跳转至

二分查找

二分查找（Binary Search）是一种在有序数组中快速查找特定元素的高效算法。其核心思想是通过不断缩小搜索范围，将时间复杂度降至 O(log n)。

  • 初始化：定义左右指针 left 和 right，分别指向数组的首尾元素。
  • 循环缩小范围：
    • 计算中间位置 mid。
    • 若中间元素等于目标值，直接返回索引。
    • 若中间元素小于目标值，说明目标在右半部分，调整 left。
    • 若中间元素大于目标值，说明目标在左半部分，调整 right。
  • 终止条件：当 left > right 时，表示未找到目标，返回 -1。

尽管二分查找思路简单清晰，但是也是挺容易出错的。下面是示例代码，返回一个int数组nums中，等于target的某一个元素的索引。

int binarySearch(int* nums, int size, int target) {
    int left = 0;
    // right=size-1, 说明查找的范围是[left, right]的左闭右闭区间。
    int right = size - 1;
    while (left <= right) {
        // NOTICE: 可以防止溢出
        int mid = left + (right - left) / 2; 
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

如果想要等于target的第一个元素/最后一个元素怎么办？这就是34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）。思路也很简单：

  1. （找第一个）如果找到相等的元素，那么继续搜索的范围是[left, mid]。（找最后一个）搜索范围则是[mid, right]。不断的缩小搜索范围直到left == right == mid。为了保证范围可以得到缩小，注意mid的取整方向。
class Solution {
public:
  int bs(int *nums, int target, int left, int right, bool start) {
    while (left <= right) {
        int mid;
        if (start) 
            mid = left + (right - left) / 2;
        else 
            mid = left + (right - left + 1) / 2;
      if (target == nums[mid]) {
        if (start)
          right = mid;
        else
          left = mid;

        if (left == right) {
          return right;
        }
      } else if (target > nums[mid]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    return -1;
  }
  vector<int> searchRange(vector<int> &nums, int target) {
    return {bs(nums.data(), target, 0, nums.size() - 1, true),
            bs(nums.data(), target, 0, nums.size() - 1, false)};
  }
};

如果我想要的是严格大于target的最小值 / 严格小于target 的最大值要怎么办？例如，对于一个单调递增数组[1,2,3,3,4,5]，我想找严格小于4的最大值（应该返回pos=3，找不到假设返回pos=-1），要怎么写？

如果直接使用缩小区间的方式，那么right=mid-1没问题，但是

  • left=mid+1可能会错过小于target的最大值。因为我们比较后发现target>nums[mid]，而不知道nums[mid+1]是什么情况。
  • left=mid，会导致可能无限循环
def binarySearch(nums: List[int], target: int):
    left, right = 0, len(nums)-1
    index = -1
    while right >= left:
        mid = (left + right) // 2
        if target > nums[mid]:
            index = mid
            left = mid + 1
        else:
            right = mid - 1
    return index