概述

想写好一个 BUG FREE 的二分查找是比较困难的，主要问题在于数组边界的定义和退出 while 循环的条件判断。写好二分查找有以下几点特别重要的点需要反复思考：

  1. 区间。左闭右开、左闭右闭关乎到 while(<= ? < ?) 里面究竟是使用 <= 还是 <。
  2. while () 内部使用 <= 还是 < 主要取决于区间的选择，如果都是闭区间，使用 <=，因为只有当 left > right 时不会漏掉任何数。

  3. 更新 left 和 right 到底是否需要 +/-1。这也取决于区间的定义，如果是右闭，那么 left = mid - 1; right = mid + 1;。

    模板

    1. 二分查找（左闭右闭）

    在一维数组中搜索目标值，找到索引值，否则返回 -1。

    1. class Solution {
    2.  public int search(int[] nums, int target) {
    3.      // 搜索范围：[left, right]
    4.      int left = 0, right = nums.length - 1;
    6.      // 当 left > right 时退出，此时搜索区间没有任务元素
    7.      while (left <= right) {
    8.          int mid = left + (right - left) / 2;
    9.          if (nums[mid] == target) {
    10.              return mid;
    11.          } else if (nums[mid] < target) {
    12.              left = mid + 1;
    13.          } else if (nums[mid] > target){
    14.              right = mid - 1;
    15.          }
    16.      }
    17.      return -1;
    18.  }
    19. }

    2. 寻找左侧边界的二分搜索

    区间：左闭右开 ```python int left_bound(int[] nums, int target) { if (nums.length == 0) return -1; int left = 0; int right = nums.length; // 注意

    // 当 left == right 时意味着不会漏掉任何数了 while (left < right) { // 注意

    1.  int mid = (left + right) / 2;
    2.  if (nums[mid] == target) {
    3.      right = mid;
    4.  } else if (nums[mid] < target) {
    5.      left = mid + 1;
    6.  } else if (nums[mid] > target) {
    7.      right = mid; // 注意
    8.  }

    } // target 比所有数都大，所以会走到最外面 if (left == nums.length) return -1;

    // 类似之前算法的处理方式 return nums[left] == target ? left : -1;

}

注意：

1. 区间是 `[)`
1. `while( < )`。每次循环的搜索区间是 `[left,rigth)`，左闭右开。而它的终止条件是 `left=right`，此时搜索区间 `[left,left)` 为空，所以可以正确终止。那为什么这里需要修改为左闭右开呢 ?  因为对于搜索左右侧边界的二分查找，这种写法比较普遍。左闭右闭的写法也是可行的。
1. `right = mid`。这是因为搜索区间是 `[left,right)`，当 `nums[mid]` 被检测后，下一步的搜索区间应该去掉 `mid` 分割的区间，即 `[Left,mid)` 或 `[mid + 1, right)`。
1. `return left`。没有返回 `-1`。这是需要对 `左侧/右侧边界` 进行解读，比如 `[2,3,4]`，`target=1`，则会返回 0，含义是数组中小于 1 的元素有 0 个。再比如 target = 8，算法会返回 4，含义是 nums 中小于 8 的元素有 4个。
1. 为什么这个算法可以搜索左侧边界 ? 关键在于对于 `nums[mid] == target` 这种情况的处理：
```python
if (nums[mid] == target) right = mid;

可见，找到 target 时并未立即返回，而是缩小搜索区间的上界 right，在区间 [left, mid) 中继续搜索，即不断向左收缩，达到锁定左侧边界的目的。

  1. 为什么返回 left 而不是 right ? 都是一样的，因为终止条件是 left==right。

  2. 如果改成 [] 可以么? 当然可以，只要明白搜索区间的含义，随便怎么更改都可以。

    3. 寻找右侧边界的二分查找算法（左闭右开）

    int right_bound(int[] nums, int target) {
 if (nums.length == 0) return -1;
 int left = 0, right = nums.length;

 while (left < right) {
     int mid = (left + right) / 2;
     if (nums[mid] == target) {
         left = mid + 1; // 注意
     } else if (nums[mid] < target) {
         left = mid + 1;
     } else if (nums[mid] > target) {
         right = mid;
     }
 }
 if (left == 0) return -1;
 return nums[left-1] == target ? (left-1) : -1;
}

    至于为什么要减一，这是搜索右侧边界的一个特殊点，关键在这个条件判断：

    if (nums[mid] == target) {
 left = mid + 1;
 // 这样想: mid = left - 1

    因为我们对 left 的更新必须是 left = mid + 1，就是说 while 循环结束时，nums[left] 一定不等于 target 了，而 nums[left-1] 可能是 target。 至于为什么 left 的更新必须是 left = mid + 1，同左侧边界搜索，就不再赘述。

二分查找细节问题在于：

  1. 到底要给 mid + 1 还是 mid-1
  2. while 到底使用 while( <= ) 还是 while( < )

使用二分查找记住以下关键点：

  1. 管他左侧还是右侧，确实搜索区间就确定一切。
  2. 搜索一个元素时，搜索区间是 [] ，即左闭右闭状态。
  3. while 条件要带等号，否则需要打补丁。
  4. if 相等就返回，其它不用管。

  5. mid 必须加减 1，因为区间两端闭。

  6. 搜索左右边界时，搜索区间要说明。

  7. 左闭右开最常见。
  8. while 要用 <。
  9. if 相等别返回，利用 mid 锁定边界。
  10. mid++ 还是 mid--，要看区间开或闭。

二分查找场景

  1. 寻找一个数
  2. 寻找左侧边界
  3. 寻找右侧边界

框架：

int binarySearch(int[] nums, int target) {
    int left = 0, right = ...;

    while(...) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            ...
        } else if (nums[mid] < target) {
            left = ...
        } else if (nums[mid] > target) {
            right = ...
        }
    }
    return ...;
}

其中 ... 标记的部分，就是可能出现细节问题的地方。注意：

  1. 计算 mid 时需要防止溢出。

  1. while(left <= right)，我们通过判断区间来解释为什么要加上 =。因为前提是 []，左闭右闭区间，如果是 <，则会漏掉比如 [2,2] 这个区间。所以要加上，当区间为 [3,2] 就能正确退出 while循环，区间也都能正常覆盖。
  2. 有些二分搜索 mid+1，有的没有 +1，这其实很好理解，也是在于区间的定义，我们都是闭区间，当 mid 不满足时，当然去搜索 [left, mid-1] 和 [mid+1, right] 。

这种写法存在局限性。比如给你有序数组 nums = [1, 2, 2, 2, 3]，target = 2，如果我想得到 target 的右侧边界，即索引 3，这样写法是无法处理的。
有人会回答，先定位 2，再线性找到下边界 3，这样做难道不可以么? 可以，但是难以保证二分查找对数级的复杂度。

二分搜索问题的泛化

首先，你得从题目中抽象出一个自变量 x，一个关于 x 的函数 f(x)，以及一个目标值 target。同时，还需要满足以下条件：

  1. f(x) 必须在 x 上单调函数。
  2. 题目是让你计算满足约束条件 f(x) == target 时的 x 的值。

    二分搜索的套路框架

    ```java // 函数 f 是关于自变量 x 的单调函数 int f(int x) { // … }

// 主函数，在 f(x) == target 的约束下求 x 的最值 int solution(int[] nums, int target) { if (nums.length == 0) return -1; // 问自己：自变量 x 的最小值是多少？ int left = …; // 问自己：自变量 x 的最大值是多少？ int right = … + 1;

while (left < right) {
    int mid = left + (right - left) / 2;
    if (f(mid) == target) {
        // 问自己：题目是求左边界还是右边界？
        // ...
    } else if (f(mid) < target) {
        // 问自己：怎么让 f(x) 大一点？
        // ...
    } else if (f(mid) > target) {
        // 问自己：怎么让 f(x) 小一点？
        // ...
    }
}
return left;

} ``` 具体来说，想要用二分搜索算法解决问题，分为以下几步：

  1. 确定 x, f(x), target 分别是什么，并写出函数 f 的代码。
  2. 找到 x 的取值范围作为二分搜索的搜索区间，初始化 left 和 right 变量。
  3. 根据题目的要求，确定应该使用搜索左侧还是搜索右侧的二分搜索算法，写出解法代码。