基本思想

  • 二分查找算法是典型的「减治思想」的应用，我们使用二分查找将待搜索的区间逐渐缩小，以达到「缩减问题规模」的目的；
  • 掌握二分查找的两种思路重点：
    • 思路 1：在循环体内部查找元素：while (left <= right)；
    • 思路 2：在循环体内部排除元素：while (left < right)。
  • 永远去想下一轮目标元素应该在哪个区间里：
    • 如果目标元素在区间 [left, mid - 1] 里，就需要设置设置 right = mid - 1；
    • 如果目标元素在区间 [mid + 1, right] 里，就需要设置设置 left = mid + 1；

      思路 1：在循环体内部查找元素（解决简单问题时有用）

      704. 二分查找

      给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

思路：
在 [low, high] 区间里查找 target。如果 nums[mid] > target，则下一轮搜索区间为 [low, mid - 1]。如果nums[mid] < target，则下一轮搜索区间为 [mid + 1, right]。

  1. class Solution {
  2.     public int search(int[] nums, int target) {
  3.         int len = nums.length;
  4.         if (len == 0) {
  5.             return -1;
  6.         }
  8.         int low = 0, high = len - 1;
  9.         while (low <= high) {
  10.             int mid = low + (high - low) / 2;
  12.             if (nums[mid] == target) {
  13.                 return mid;
  14.             } else if (nums[mid] > target) {
  15.                 high = mid - 1;
  16.             } else {
  17.                 low = mid + 1;
  18.             }
  19.         }
  21.         return -1;
  22.     }
  23. }

练习：

1095. 山脉数组中查找目标值

思路 2：在循环体内部排除元素（在解决复杂问题时非常有用）

  1. public int search(int[] nums, int left, int right, int target) {
  2.     // 在区间 [left, right] 里查找目标元素
  3.     while (left < right) {
  4.         // 选择中间数时下取整
  5.         int mid = left + (right - left) / 2;
  6.         if (check(mid)) {
  7.             // 下一轮搜索区间是 [mid + 1, right]
  8.             left = mid + 1;
  9.         } else {
  10.             // 下一轮搜索区间是 [left, mid]
  11.             right = mid;
  12.         }
  13.     }
  14.     // 退出循环的时候，程序只剩下一个元素没有看到，视情况，是否需要单独判断 left（或者 right）这个下标的元素是否符合题意
  15. }
public int search(int[] nums, int left, int right, int target) {
    // 在区间 [left, right] 里查找目标元素
    while (left < right) {
        // 选择中间数时上取整
        int mid = left + (right - left + 1) / 2;
        if (check(mid)) {
            // 下一轮搜索区间是 [left, mid - 1]
            right = mid - 1;
        } else {
            // 下一轮搜索区间是 [mid, right]
            left = mid;
        }
    }
    // 退出循环的时候，程序只剩下一个元素没有看到，视情况，是否需要单独判断 left（或者 right）这个下标的元素是否符合题意
}
  • 核心思想：把待搜索的目标元素放在最后判断，每一次循环排除掉不存在目标元素的区间，目的依然是确定下一轮搜索的区间；

  • 特征：while (left < right)，这里使用严格小于 < 表示的临界条件是：当区间里的元素只有 2 个时，依然可以执行循环体。换句话说，退出循环的时候一定有 left == right 成立，这一点在定位元素下标的时候极其有用；

    两个二分查找法思想的使用建议

  • 简单问题使用思路 1：即要找的那个数的性质特别简单：== 的情况好写，< 的情况好写，> 的情况也好写的时候；

  • 复杂问题使用思路 2：即要找的那个数的性质有点复杂，可能需要借助单调性。用思路 2 就可以把两个边界逐渐向中间收缩，直至找到目标元素；
  • 区别：
    • 思路 1 循环体内部有 3 个分支，一定有一个分支用于退出循环或者直接返回，因此无需「后处理」；
    • 思路 2 循环体内部有 2 个分支，两个分支都在缩小待搜索区间，退出循环以后，可能需要「后处理」。