二分查找模板

2023-08-06

二分查找

二分查找可用于在有序序列中搜索或确定元素或枢轴。这里我们有三种使用二分查找的场景。

在唯一元素数组中查找元素

1
2
3
4
5
6
7
8
9
10
11
int basic_binary_search(int[] arr, int target) {
    int left = 0;
    int right = n;
    while(left <=  right) {
        int mid = left + (right - left) / 2;
        if(arr[mid] == target) return mid;
        else if(arr[mid] > target) right = mid - 1;
        else left = mid + 1;
    }
    return -1;
}

有时当数组中有重复元素时，我们可能想要找到目标元素的左边界或右边界，这时情况会变得复杂。但我们仍然有方法来做到这一点。

查找左边界

1
2
3
4
5
6
7
8
9
10
11
12
int left_bound_binary_search(int[] arr, int target) {
    int left = 0;
    int right = n;
    while(left <=  right) {
        int mid = left + (right - left) / 2;
        if(arr[mid] == target) right = mid - 1;
        else if(arr[mid] > target) right = mid - 1;
        else left = mid + 1;
    }
    if(left < 0  || left >= arr.length) return -1;
    return arr[left] == target ? left : -1;
}

我们以上面的代码为例。首先我们需要定义搜索范围。

  • 如果我们使用 while(left <= right)，这意味着我们的搜索范围是 。
  • 如果我们使用 while(left < right)，这意味着我们的搜索范围是 ，因为left永远不会达到初始的right值。
1
if(arr[mid] == target) right = mid - 1;

对于这一行，当我们发现目标值等于 arr[mid] 时，我们不返回 mid，而是缩小右边界，这意味着对于 ，我们有 arr[i] >= target。另一方面，对于 left，它最终会进入 arr[i] >= target 的域，或者它会超出数组的范围。排除超出范围的情况后，我们有两种情况：

  1. arr[i] = target
  2. arr[i] > target

这是为了检查目标值是否存在于数组中。

查找右边界

int right_bound_binary_search(int[] arr, int target) {
    int left = 0;
    int right = n;
    while(left <=  right) {
        int mid = left + (right - left) / 2;
        if(arr[mid] == target) return left = mid + 1;
        else if(arr[mid] > target) right = mid - 1;
        else left = mid + 1;
    }
    return -1;
}