Fl0w3r

carpe diem

Binary Search

Posted on In
2.7k 5 mins.

引言

Array是最基础也是最常见的数据结构，以下我们会介绍array题目中常用的二分查找（binary search）方法，可以用于解决一系列常见的array题目。本章会讲解二分查找的原则和模板，然后再结合题目帮助大家深入理解如何应用二分查找。

二分查找

一种针对有序区间内的 $O(\log N)$ 搜索方式，最常见于已经排好序的 Array。

int binarySearch(vector<int>& arr, int k) {
	int left = 0, right = arr.size() - 1;
  // int mid = (left + right) / 2;
  int mid = left + (right - 1) / 2;
  
  if(arr[mid] == k)
    return mid;
  else if(arr[mid] > k)
    right = mid - 1;
  else
    left = mid + 1;
  
  return -1;
}

那我们变换一下场景，是否还能套用上面的模板呢？

比如我要找最接近 4 的数，最终我们的 mid 会回归到 2 上，但我们肉眼可见 5 才是最接近 4 的数，显然模板就不适用了。

基本原则

  1. 每次都要缩减搜索区域

    Shrink the search space every iteration (or recursion)

  2. 每次缩减不能排除潜在答案

    Cannot exclude potential answers during each shrinking

针对模板

查找准确值

  • 循环条件：left <= right

  • 缩减搜索空间

    left = mid + 1;
    right = mid - 1;

查找模糊值

  • 循环条件：left < right

  • 缩减搜索空间

    left = mid;
    right = mid - 1;
    // or
    left = mid + 1;
    right = mid;
First Occurance of 2

我们现在需要找到 2 第一次出现的位置，这里缩减搜索空间的策略选择 left = mid + 1、right = mid。

我们可以肉眼看到第二个序列中 2 确实是第一次出现的位置，但如果是第一个序列 2 不是第一个出现的，如果我们 right = mid - 1 违背了每次缩减不能排除潜在答案的原则，我们还需要搜索，但还不能排除当前的 2 就不是答案，所以需要保留 right = mid。

int binarySearch(vector<int> arr, int k) {
	int left = 0, right = arr.size() - 1;
  
  while(left < right) {
    int mid = left + (right - left)/2;
    if(arr[mid] < k)
      left = mid + 1;
    else
      right = mid;
  }
  return left;
}
Last Occurance of 2

这回我们颠倒过来找 2 最后出现的位置，这次我们的缩减空间策略选择 left = mid、right = mid - 1。

现在大家应该已经理解了，同样遇到 2 我们既需要继续向右搜索寻找最后位置的 2，也需要把目前的 2 保留下来作为潜在答案。

int binarySearch(vector<int> arr, int k) {
	int left = 0, right = arr.size() - 1;
  
  while(left < right) {
    int mid = left + (right - left)/2;
    if(arr[mid] > k)
      left = mid;
    else
      right = mid - 1;
  }
  
	return -1;
}

通用模板

  • 循环条件：left < right - 1

  • 缩减搜索空间

    left = mid;
    right = mid;
Closest to 2

这个例子中 left 在 1 上，right 在 4 上，那为什么不能按之前做法走呢？根据我们之前的做法，1 < 2 不管停在哪儿都是往右走，最后 left 和 right 都等于 4 结束，但很明显 1 更靠近2。

万用型的好处是最后会留下两个值，我们可以比较一下最后返回 left 还是 right。

int binarySearch(vector<int> arr, int k) {
	int left = 0, right = arr.size() - 1;
  
  while(left < right - 1) {
    int mid = left + (right - left)/2;
    if(arr[mid] > k)
      left = mid;
    else
      right = mid;
  }
  
	if(arr[right] < k)
    return right;
  else if(arr[left] > k)
    return left;
  else
  	return k - arr[left] < arr[right] - k ? left : right;
}

实践应用

例题 1062. Longest Repeating Substring

暴力查找 $O(n^3)$

  • 所有 substring –> $O(n^2)$
  • hashset 查重 substring –> $O(n)$

有序区间：Length of the Longest Repeating Substring –> [0, n]

f(x)：verify if length x is a valid answer for the LRS

  • mid = left + (right - left + 1)/2
  • case 1: f(mid) is valid –> left = mid
  • case 2: f(mid) not valid –> right = mid - 1
class Solution {
public:
    int longestRepeatingSubstring(string s) {
        int left = 0, right = s.length() - 1;
        
        while(left < right) {
            int mid = left + (right - left)/2;
            
            if(f(s, mid))
                left = mid;
            else
                right = mid - 1;
        }
   }
}

总结

  • Binary Search 是一个在 $O(\log N)$ 时间在有序区间实现搜索的算法

  • 基本原则

    1. 每次都要缩减搜索区域

      Shrink the search space every iteration (or recursion)

    2. 每次缩减不能排除潜在答案

      Cannot exclude potential answers during each shrinking

  • 三种变种

大家可以通过更多类似题目进行练习：

  1. Split Array Largest Sum (410)
  2. Divide Chocolate (1231)
  3. Peak Index in a Mountain Array (852)
  4. Capacity To Ship Packages Within D Days (1011)
  5. Maximum Side Length of a Square with Sum Less than or Equal to Threshold (1292)
Related Posts