BinarySearch Template

Posted on Edited on Views:

1、标准二分查找的适用场景：数组元素有序且不重复

我们以 “搜索一个数，如果存在，返回其索引，否则返回 -1” 为例，给出标准二分查找的模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 二分查找某个数
int binarySearch(vector<int> nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) { // 注意
      	// 防止溢出
        int mid = left + ((right - left) >> 1);
        if (nums[mid] == target)
            return mid;
        // 收缩右边界
        else if (nums[mid] > target)
            right = mid - 1;
        // 收缩左边界
        else // (nums[mid] < target)
            left = mid + 1;
    }
    return -1;
}

2、二分查找边界

附视频链接：
二分查找为什么总是写错？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 二分查找某个数的左边界
int binarySearch(vector<int> nums, int target) {
    int left = -1, right = nums.size();
    while (left+1 != right) { // 注意
        int mid = left + ((right - left)) >> 1;
        // 收缩左边界
        if (nums[mid] < target) {
            left = mid;
        } else { // nums[mid] >= target
            // 收缩右边界
            right = mid;
        }
    }

    // 打个补丁
    return nums[left] == target ? left : -1;
}

3、二分查找极值点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int binarySearch(vector<int> nums){
  int left = 0, right = nums.size() - 1, mid;
  while(left <= right) {
    mid = left + ((right - left) >> 1);
    // 极值点
    if (nums[mid] > nums[mid + 1] && nums[mid] > nums[mid - 1]) {
      return mid;
    } else if (nums[mid] > nums[mid + 1]){
      // 极值点在 mid 左边
      right = mid - 1;
    } else {
      // 极值点在 mid 右边
      left = mid + 1;
    }
  }
  return -1;
}

References:

⚡『LeetCode-Offer』二分查找三大模板，照着抄就行！