[LeetCode] 二分查找模板 binary search

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

如下模板是用Java实现的

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

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

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

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

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

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

这 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)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

LeetCode 题目总结


[LeetCode] 二分查找模板 binary search
https://shurui91.github.io/posts/3220296722.html
Author
Aaron Liu
Posted on
January 12, 2021
Licensed under