本文共 2321 字，大约阅读时间需要 7 分钟。

寻找第一个的满足条件的位置

例如nums = [5,7,7,8,8,10], target = 8，第一个的满足条件的位置=3.

和查找一个数类似， 我们仍然套用查找一个数的思维框架和代码模板。

思维框架

• 首先定义搜索区间为 [left, right]。
• 终止搜索条件为 left > right。
• 循环体内，我们不断计算 mid ，并将 nums[mid] 与 目标值比对。
  • 如果 nums[mid] 等于目标值， 则收缩右边界，我们找到了一个备胎，由于我们要找第 1 个位置，此时我们应该向左边继续查找；（注意这里不一样）
  • 如果 nums[mid] 小于目标值， 说明目标值在 mid 右侧，这个时候搜索区间可缩小为 [mid + 1, right]
  • 如果 nums[mid] 大于目标值， 说明目标值在 mid 左侧，这个时候搜索区间可缩小为 [left, mid - 1]
• 由于不会提前返回，因此我们需要检查最终的 left，看 nums[left]是否等于 target。
  • 如果不等于 target，或者 left 出了右边边界了，说明至死都没有找到一个备胎，则返回 -1.
  • 否则返回 left 即可，备胎转正。

代码模板:

实际上 nums[mid] > target 和 nums[mid] == target 是可以合并的。我这里为了清晰，就没有合并，大家熟悉之后合并起来即可。

def findFirstPosition(nums, target):    l, r = 0, len(nums) - 1    while l <= r:        mid = (l + r) // 2        if nums[mid] == target:            # ① 不可以直接返回，应该继续向左边找，即 [left..mid - 1] 区间里找            # 收缩右边界            r = mid - 1;        elif nums[mid] < target:  # 应该继续向右边找,搜索区间变为 [mid+1, right]            l = mid + 1        else: #  nums[mid] > target ,应该继续向左边找 ,搜索区间变为 [left, mid - 1]            r = mid - 1    # 此时 left 和 right 的位置关系是 [right, left]，注意上面的 ①，此时 left 才是第 1 次元素出现的位置    # 因此还需要特别做一次判断    if l >= len(nums) or nums[l] != target:         return -1    return l

寻找最后一个的满足条件的值

例如nums = [5,7,7,8,8,10], target = 8，最后一个的满足条件的位置=4.

和查找一个数类似， 我们仍然套用查找一个数的思维框架和代码模板。

思维框架

• 首先定义搜索区间为 [left, right]。

• 终止搜索条件为 left > right。

• 循环体内，我们不断计算 mid ，并将 nums[mid] 与 目标值比对。

  • 如果 nums[mid] 等于目标值， 则收缩左边界，我们找到了一个备胎，继续看看右边还有没有了
  • 如果 nums[mid] 小于目标值， 说明目标值在 mid 右侧，这个时候搜索区间可缩小为 [mid + 1, right]
  • 如果 nums[mid] 大于目标值， 说明目标值在 mid 左侧，这个时候搜索区间可缩小为 [left, mid - 1]

• 由于不会提前返回，因此我们需要检查最终的 right，看 nums[right]是否等于 target。

  • 如果不等于 target，或者 right 出了左边边界了，说明至死都没有找到一个备胎，则返回 -1.
  • 否则返回 right 即可，备胎转正。

代码模板:

实际上 nums[mid] < target 和 nums[mid] == target 是可以合并的。我这里为了清晰，就没有合并，大家熟悉之后合并起来即可。

def findLastPosition(nums, target):    # 左右都闭合的区间 [l, r]    l, r = 0, len(nums) - 1    while l <= r:        mid = (l + r) // 2        if nums[mid] == target:            # 只有这里不一样：不可以直接返回，应该继续向右边找，即 [mid + 1, right] 区间里找            # 收缩左边界            l = mid + 1;        # 应该继续向右边找,搜索区间变为 [mid+1, right]        elif nums[mid] < target:             l = mid + 1        # 应该继续向左边找,搜索区间变为 [left, mid - 1]        elif nums[mid] > target:             r = mid - 1    if r < 0 or nums[r] != target: return -1    return r

参考

力扣（LeetCode） (leetcode-cn.com)]

转载地址：http://sdyzi.baihongyu.com/