二分查找

针对有序是数据进行高效查找，可以使用二分查找，时间复杂度为 O(n) ，实现上类似分治思想，每次都和区间中间的值比较 然后缩小查找区间，知道找到目标元素或者区间缩小为 0。

二分查找依赖的是顺序表结构，即数组，在内存中拥有连续的数据，使用场景有一定的局限性：

• 数据必须是有序的

• 数据量太小的，无需使用二分查找；如果比较本身比较耗时，可以考虑使用二分查找减少比较次数

• 数据量太大也不宜使用二分查找，需要申请大量的 连续 内存

小技巧

计算中点位置时，可以用 mid = left + (right - left) / 2 ，防止数字过大时溢出

---

查找某个目标元素

递增序列，无重复元素，查找某个元素 target 在数组的中的下标。

def binary_search(nums, target):

    length = len(nums)
    if length == 0:
        return -1

    left, right = 0, length - 1

    while left <= right:
        mid = left + (right - left) / 2
        if nums[mid] == target:
            return mid
        # 查找区间为 [mid+1, right]
        elif nums[mid] < target:
            left = mid + 1
        # 查找区间为 [left, mid-1]
        elif nums[mid] > target:
            right = mid - 1
    return -1

---

查找某个目标第一个或左后一个出现的位置

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置:

输入: nums = [5,7,7,8,8,10], target = 8

输出: [3,4]

输入: nums = [5,7,7,8,8,10], target = 6

输出: [-1,-1]a

查找 target 出现的第一个位置

小技巧

以查找 target 出现的第一个位置为例（同理，适用于查找最后一个位置）

nums[mid] >= target ，我们重点分析一下这一行代码：

• 当 nums[mid] > target 时，显然我们要缩小查找区间，将搜索的右边界往左移动即 right = mid - 1

• 当 nums[mid] == target 时，因为我们要查找元素出现的第一个位置，此时我们无法确定当前的 target 是否为第一个出现， 所以我们也要向左缩小区间（因为数组是升序的，第一个位置不可能出现在当前 target 之后）；

  我们在第一次找到 target 后通过判断通过 index 保存了其坐标

  右边界在左移以后：如果下一个扫描区间 [left, mid-1] 里面仍然有 target，我们会在后面的逻辑里更新 index 的值； 如果下个扫描区间里不再包含 target，那么就会一直执行 left = mid + 1 ，直到循环退出

• 如果 target 不存在，返回默认 index

def left_bound(nums, target):
    length = len(nums)
    if length == 0:
        return -1

    left, right = 0, length - 1
    index = -1

    while left <= right:
        mid = left + (right - left) / 2
        if nums[mid] >= target:
            right = mid - 1
        else:
            left = mid + 1

        # 保存并更新 target 坐标
        if nums[mid] == target:
            index = mid
    return index

---

查找 target 出现的最后一个位置

def right_bound(nums, target):
    length = len(nums)
    if length == 0:
        return -1

    left, right = 0, length - 1
    index = -1

    while left <= right:
        mid = left + (right - left) / 2
        if nums[mid] <= target:
            left = mid + 1
        else:
            right = mid - 1

        if nums[mid] == target:
            index = mid
    return index