转载自

模板1（简单问题用）

Java代码

  1. class Solution {
  3.     public int search(int[] nums, int target) {
  4.         // 特殊用例判断
  5.         int len = nums.length;
  6.         if (len == 0) {
  7.             return -1;
  8.         }
  9.         // 在 [left, right] 区间里查找 target
  10.         int left = 0;
  11.         int right = len - 1;
  12.         while (left <= right) {
  13.             // 为了防止 left + right 整形溢出，写成如下形式
  14.             int mid = left + (right - left) / 2;
  16.             if (nums[mid] == target) {
  17.                 return mid;
  18.             } else if (nums[mid] > target) {
  19.                 // 下一轮搜索区间：[left, mid - 1]
  20.                 right = mid - 1;
  21.             } else {
  22.                 // 此时：nums[mid] < target，下一轮搜索区间：[mid + 1, right]
  23.                 left = mid + 1;
  24.             }
  25.         }
  26.         return -1;
  27.     }
  28. }

说明：

  • 最简单的二分查找思路：在一个有序数组里查找目标元素。特别像以前电视「猜价格」上的猜价格游戏：运气好，一下子猜中，如果主持人说猜高了，下一步就应该往低了猜，如果主持人说猜低了，下一步就应该就往高了猜。这个思路把待搜索区间[left, right]分为 3 个部分：
    • mid 位置（只有 1 个元素）；
    • [left, mid - 1] 里的所有元素；
    • [mid + 1, right] 里的所有元素；
  • 于是，二分查找就是不断地在区间[left, right]里根据left和right的中间位置mid = (left + right) / 2的元素大小，也就是看nums[mid]与target的大小关系：
    • 如果 nums[mid] == target ，返回 mid；
    • 如果 nums[mid] < target ，由于数组有序，mid 以及 mid 左边的所有元素都小于 target，目标元素可能在区间 [mid + 1, right] 里，因此设置 left = mid + 1；
    • 如果 nums[mid] > target ，由于数组有序，mid 以及 mid 右边的所有元素都大于 target，目标元素可能在区间 [left, mid - 1] 里，因此设置 right = mid - 1。
  • 循环体内一定有 3 个分支，并且第 1 个分支一定用于退出循环，或者直接返回目标元素；
  • 退出循环以后，left 和 right 的位置关系为 [right, left] ，返回 left 或者 right 需考虑清楚。

注意事项：

  • 许多刚刚写的朋友，经常在写left = mid + 1;还是写right = mid - 1;上感到困惑，一个行之有效的思考策略是：永远去想下一轮目标元素应该在哪个区间里；
    • 如果目标元素在区间 [left, mid - 1] 里，就需要设置设置 right = mid - 1；
    • 如果目标元素在区间 [mid + 1, right] 里，就需要设置设置 left = mid + 1；
  • 考虑不仔细是初学二分法容易出错的地方，这里切忌跳步，需要仔细想清楚每一行代码的含义；
  • 循环可以继续的条件是 while (left <= right)，特别地，当 left == right 即当待搜索区间里只有一个元素的时候，查找也必须进行下去；
  • int mid = (left + right) / 2; 在 left + right 整形溢出的时候，mid 会变成负数，回避这个问题的办法是写成 int mid = left + (right - left) / 2;。

模板2（复杂问题用）

这个版本的模板推荐使用的原因是：需要考虑的细节最少，编码时不容易出错。

根据中间数被分到左边还是右边，一共就以下两种写法。不能死记硬背，应该通过多练习，理解当看到 left = mid 的时候，将取中间数的取法改成上取整的原因。

Java代码

  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. }
  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 + 1) / 2;
  6.         if (check(mid)) {
  7.             // 下一轮搜索区间是 [left, mid - 1]
  8.             right = mid - 1;
  9.         } else {
  10.             // 下一轮搜索区间是 [mid, right]
  11.             left = mid;
  12.         }
  13.     }
  14.     // 退出循环的时候，程序只剩下一个元素没有看到，视情况，是否需要单独判断 left（或者 right）这个下标的元素是否符合题意
  15. }

理解模板代码的要点：

  • 核心思想：虽然模板有两个，但是核心思想只有一个，那就是：把待搜索的目标元素放在最后判断，每一次循环排除掉不存在目标元素的区间，目的依然是确定下一轮搜索的区间；
  • 特征：while (left < right)，这里使用严格小于 < 表示的临界条件是：当区间里的元素只有 2 个时，依然可以执行循环体。换句话说，退出循环的时候一定有 left == right 成立，这一点在定位元素下标的时候极其有用；
  • 在循环体中，先考虑nums[mid]在满足什么条件下不是目标元素，进而考虑两个区间[left, mid - 1]以及[mid + 1, right]里元素的性质，目的依然是确定下一轮搜索的区间；
    • 注意 1：先考虑什么时候不是解，是一个经验，在绝大多数情况下不易出错，重点还是确定下一轮搜索的区间，由于这一步不容易出错，它的反面（也就是 else 语句的部分），就不用去考虑对应的区间是什么，直接从上一个分支的反面区间得到，进而确定边界如何设置；
  • 根据边界情况，看取中间数的时候是否需要上取整；
    • 注意 2： 这一步也依然是根据经验，建议先不要记住结论，在使用这个思想解决问题的过程中，去思考可能产生死循环的原因，进而理解什么时候需要在括号里加 1 ，什么时候不需要；
  • 在退出循环以后，根据情况看是否需要对下标为 left 或者 right 的元素进行单独判断，这一步叫「后处理」。在有些问题中，排除掉所有不符合要求的元素以后，剩下的那 1 个元素就一定是目标元素。如果根据问题的场景，目标元素一定在搜索区间里，那么退出循环以后，可以直接返回 left（或者 right）。

以上是这两个模板写法的所有要点，并且是高度概括的。请读者一定先抓住这个模板的核心思想，在具体使用的过程中，不断地去体会这个模板使用的细节和好处。只要把中间最难理解的部分吃透，几乎所有的二分问题就都可以使用这个模板来解决，因为「减治思想」是通用的。好处在这一小节的开篇介绍过了，需要考虑的细节最少。

学习建议：

  • 一定需要多做练习，体会这（两）个模板的使用；
  • 先写分支逻辑，再决定中间数是否上取整；

  • 在使用多了以后，就很容易记住，只要看到 left = mid ，它对应的取中位数的取法一定是 int mid = left + (right - left + 1) / 2;。

    使用建议

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

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