[LeetCode] 二分查找模板 binary search

二分法是算法题里面一个比较基础但是很容易错的概念，一开始练习的时候由于不熟悉二分法的套路，反复出现死循环或者目标值找错，非常影响做题心情。我总结了如下几个模板。原则上这里的模板无论你使用哪一个，都可以解决二分法类型的问题，只不过有一些题目，比如寻找一个最大值/最小值的，可能某一个模板更适合，需要判断的条件较少。

如下模板是用Java实现的

模板一，找有序数组中是否存在一个目标值。注意 right 指针一开始定义是在数组下标范围内的，所以while的条件才能写成 <=。

 1 class Solution {
 2     public int binarySearch2(int[] nums, int target) {
 3         // left和right都在数组下标范围内
 4         // [left, right]
 5         int left = 0;
 6         int right = nums.length - 1;
 7         // while循环跳出的条件是left < right
 8         // 所以如果没找到target的话，也不需要特判了
 9         while (left <= right) {
10             int mid = left + (right - left) / 2;
11             if (nums[mid] == target) {
12                 return mid;
13             } else if (nums[mid] < target) {
14                 left = mid + 1;
15             } else {
16                 right = mid - 1;
17             }
18         }
19         // 如果没找到就只能返回-1
20         return -1;
21     }
22 }

模板二，适合判断当前 index 和 index + 1 之间的关系。right 指针一开始的定义是在数组下标范围外的，[left, right)，所以在需要移动 right 指针的时候不能写成 right = mid - 1。这样会遗漏掉一些下标的判断。

 1 class Solution {
 2     public int binarySearch3(int[] nums, int target) {
 3         // right不在下标范围内
 4         // [left, right)
 5         int left = 0;
 6         int right = nums.length;
 7         // while循环跳出的条件是left == right
 8         // 这个模板比较适合判断当前index和index + 1之间的关系
 9         // left < right, example, left = 0, right = 1
10         while (left < right) {
11             int mid = left + (right - left) / 2;
12             if (nums[mid] == target) {
13                 return mid;
14             } else if (nums[mid] < target) {
15                 left = mid + 1;
16             } else {
17                 // 因为搜索范围是左闭右开所以这里不能-1
18                 right = mid;
19             }
20         }
21         // 最后的特判
22         if (left != nums.length && nums[left] == target) {
23             return left;
24         }
25         return -1;
26     }
27 }

模板三，适用于查找有序数组中某个元素是否存在。若不存在，往往题目要求返回 -1。注意 right 指针一开始定义是在数组下标范围内的，while条件不满足的时候，left + 1 == right，两下标应该指向某个下标 i 和 i + 1。这样如果有什么特殊的值需要判断，应该不是 left 就是 right 了。

 1 class Solution {
 2     public int binarySearch1(int[] nums, int target) {
 3         // left和right都在数组下标范围内
 4         // [left, right]
 5         int left = 0;
 6         int right = nums.length - 1;
 7         // 举例，start - 0, end = 3
 8         // 中间隔了起码有start + 1和start + 2两个下标
 9         // 这样跳出while循环的时候，start + 1 == end
10         // 才有了最后的两个判断
11         while (left + 1 < right) {
12             int mid = left + (right - left) / 2;
13             if (nums[mid] == target) {
14                 return mid;
15             } else if (nums[mid] < target) {
16                 left = mid;
17             } else {
18                 right = mid;
19             }
20         }
21         // 特判
22         if (nums[left] == target) {
23             return left;
24         }
25         if (nums[right] == target) {
26             return right;
27         }
28         // 如果没找到就只能返回-1
29         return -1;
30     }
31 }

如上三个模板的比较如下图

这 3 个模板的不同之处在于：

左、中、右索引的分配。
循环或递归终止条件。
后处理的必要性。
模板 #1 和 #3 是最常用的，几乎所有二分查找问题都可以用其中之一轻松实现。模板 #2 更 高级一些，用于解决某些类型的问题。

这 3 个模板中的每一个都提供了一个特定的用例

模板 #1 (left <= right)

二分查找的最基础和最基本的形式。
查找条件可以在不与元素的两侧进行比较的情况下确定（或使用它周围的特定元素）。
不需要后处理，因为每一步中，你都在检查是否找到了元素。如果到达末尾，则知道未找到该元素。

模板 #2 (left < right)

一种实现二分查找的高级方法。
查找条件需要访问元素的直接右邻居。
使用元素的右邻居来确定是否满足条件，并决定是向左还是向右。
保证查找空间在每一步中至少有 2 个元素。
需要进行后处理。 当你剩下 1 个元素时，循环 / 递归结束。 需要评估剩余元素是否符合条件。

模板 #3 (left + 1 < right)

实现二分查找的另一种方法。
搜索条件需要访问元素的直接左右邻居。
使用元素的邻居来确定它是向右还是向左。
保证查找空间在每个步骤中至少有 3 个元素。
需要进行后处理。 当剩下 2 个元素时，循环 / 递归结束。 需要评估其余元素是否符合条件。

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/binary-search/xewjg7/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。