在一个有序的序列中,使用二分法能够以logn的时间找到目标元素。
二分的核心思想是“减治”,利用排除法一步一步将区间排除,将区间缩小,最终将目标找到。
# 基本二分法:查找元素的位置
在升序数组中查找target,若数组中有该target,返回target所在数组的下标(若数组中target不唯一,则返回其中一个下标),否者返回-1。
public int binarySearch(int nums[], int target){
int left = 0;
int right = nums.length - 1; // 在[0, num.length)中查找target元素,同[0,nums.length - 1]
while(left <= right){ // 当start大于end时结束循环,此时表示没有查找到target元素
int mid = left + (right - left) / 2;
if(nums[mid] == target){ // 查找到target,返回下标
return mid;
}else if(nums[mid] > target){
// 若中值对应的元素大于target,表明[mid, right]元素都大于target,
// 排除掉此区间,去数组的左半部分[left, mid - 1]查找
right = mid - 1;
}else if(nums[mid] < target){
// 若中值对应元素小于target,表明[left, mid]元素都小于target,
// 排除掉此区间,去数组的右半部分[mid+1, right]查找
left = mid + 1;
}
}
return -1;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
这是最常用的二分搜索, 用来在有序数组中寻找特定元素;
此外,left和right指针也有妙用,试想若最后没有找到target,left的值就等于right + 1,left属于[0, n],left指向元素可以插入的位置,即指向数组中比target大的第一个元素的位置,当left 等与n时,说明target比所有元素都要大。
right属于[-1, n - 1],right指向比target小的最大元素的位置,若right等于-1,说明数组中没有比target小的元素。
活用left和right两个指针,可以用来解决很多问题。
# 35. 搜索插入位置 (opens new window)
很明显,我们要找target要插入的位置,就是要找到比target第一个大的元素的位置,在基本二分法中,left最后所指向的位置正好就是target插入的位置。
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left <= right){
int mid = left + (right - left) / 2;
if(nums[mid] == target){
// 这里也可以直接返回mid
left = mid;
break;
}
if(nums[mid] > target){
right = mid - 1;
}else{
left = mid + 1;
}
}
return left;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 74. 搜索二维矩阵 (opens new window)
我们可以使用对矩阵第一列进行二分,利用right指针找到矩阵第一列元素中比target小的最大元素的位置,根据right的值分以下两种情况:
若right等于-1,说明矩阵中没有比target还小的元素,此时返回false,
若right不等与-1,我们可以从matrix/[right]/[0-n]中去查找元素target,此时用基本二分法去查找target元素。
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;
if(m == 0)
return false;
int n = matrix[0].length;
if(n == 0)
return false;
int left = 0;
int right = m - 1;
while(left <= right){
int mid = left +(right - left) / 2;
if(matrix[mid][0] == target)
return true;
if(matrix[mid][0] > target){
right = mid - 1;
}else if(matrix[mid][0] < target){
left = mid + 1;
}
}
if(right == -1)
return false;
int index = right;
left = 0;
right = n - 1;
// 在矩阵right行去寻找target
while(left <= right){
int mid = left + (right - left) / 2;
if(matrix[index][mid] == target)
return true;
if(matrix[index][mid] < target){
left = mid + 1;
}else{
right = mid - 1;
}
}
return false;
}
}
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
32
33
34
35
36
37
38
39
当然我们也可以使用left指针寻找第一个比target大的元素,在用二分去搜索left所指的矩阵对应行。
# 69. x 的平方根 (opens new window)
从题意可以知道,我们要找到的x的平方根是去掉小数的,假设x的平方根是mid,mid * mid = x,假设我们要返回的数是num,num 应该满足 num <= mid,也就是说我们要在0,1,2.....x(都是整数)中找到小于或等于mid的最大元素,也即是我们的right指针所指的数。
class Solution {
public int mySqrt(int x) {
int left = 0;
int right = x;
while(left <= right){
int mid = left + (right - left) / 2;
// 注意当mid过大时会发生溢出
long t = (long)mid * mid;
if(t == x ){
return mid;
}
if(t < x){
left = mid + 1;
}else{
right = mid - 1;
}
}
return right;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
注意我们不能在小数范围内去寻找mid,然后再去掉小数,不能这样做的原因是因为计算机中浮点型表示是不精确的,100的开方的计算结果可能是9.999999...,显然去掉小数点后是不正确的。
# 查找元素的左右边界
# 34. 在排序数组中查找元素的第一个和最后一个位置 (opens new window)
寻找元素的左边界
// left值为target第一次出现或者第一个比target大的位置,left = [0, n]
public int leftBound(int[] nums, int target){
int left = 0;
int right = nums.length - 1;
while(left <= right){
int mid = left + (right - left) / 2;
if(target <= nums[mid]){
right = mid - 1;
}else{
left = mid + 1;
}
}
if(left == nums.length || nums[left] != target)
return -1;
return left;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
寻找元素的右边界
// right值为target最后一次出现或者第一个比target小的位置,right = [-1, n-1]
public int rightBound(int[] nums, int target){
int left = 0;
int right = nums.length - 1;
while(left <= right){
int mid = left + (right - left) / 2;
if(target < nums[mid]){
right = mid - 1;
}else{
left = mid + 1;
}
}
if(right == -1 || nums[right] != target)
return -1;
return right;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 二分法变形
# 153. 寻找旋转排序数组中的最小值 (opens new window)
理解了二分法的核心是排除法,写一些变形的二分也信手拈来,
class Solution {
public int findMin(int[] nums) {
int left = 0;
int right = nums.length - 1;
int start = 0;
int end = right;
if(nums[start] <= nums[end]) // 整体有序的情况
return nums[start];
while(left < right){
int mid = left + (right - left) / 2;
// 左侧局部有序,左侧不存在最小值,排除[left, mid]
if(nums[mid] >= nums[start]){
left = mid + 1;
}else{
// 右侧局部有序时,排除[mid+1,right],mid可能为答案,不能排除
right = mid;
}
}
return nums[left];
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 面试题11. 旋转数组的最小数字 (opens new window)
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如,数组 [3,4,5,1,2]
为 [1,2,3,4,5]
的一个旋转,该数组的最小值为1。
示例 1:
输入:[3,4,5,1,2]
输出:1
2
示例 2:
输入:[2,2,2,0,1]
输出:0
2
与上一题相比,这里的数组多了可以有重复元素这个条件,此时就无法根据numbers[mid] <= numbers[right]
来判断数组左右的有序性,但可以用numbers[mid] < numbers[right]
这个严格条件来判断,如果numbers[mid] == numbers[right]
,很明显可以排除掉right处的元素,因为如果当前right是最小元素,数组中还存在numbers[mid],这个也是最小元素。
class Solution {
public int minArray(int[] numbers) {
int left = 0;
int right = numbers.length - 1;
while(left < right){
int mid = left + (right - left) / 2;
// 此处先判断右侧是否局部有序可以解决数组整体有序的特殊情况
if(numbers[mid] < numbers[right]){
// 右侧数组局部有序,可以排除掉[mid+1, right]
right = mid;
}else if(nums[mid] > numbers[right]){
// 左侧数组局部有序,可以排除掉[left, mid]
left = mid + 1;
}else{
right--;
}
}
return numbers[left];
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 一些不明显的二分题
# LCP 12. 小张刷题计划 (opens new window)
# 5438. 制作 m 束花所需的最少天数 (opens new window)
# 1300. 转变数组后最接近目标值的数组和 (opens new window)
# 378. 有序矩阵中第K小的元素 (opens new window)
# 二分法小结
- 初始化left和right指针,确定target存在的范围;
- 确定使用
while(left <= right)
还是while(left < right)
,区分两者的区别; - 根据中值排除区间,缩小范围;
- 处理返回。
while(left <= right)
与 while(left < right)
的区别?
while(left <= right)
遇到target直接返回,若没有找到target,最终left = right + 1,left的取值范围为[left, right+1],right取值范围为[left-1, right];
while(left < right)
遇到target不返回,最终left = right,left和right的取值范围都为[left, right];
参考链接
- https://leetcode-cn.com/problems/search-insert-position/solution/te-bie-hao-yong-de-er-fen-cha-fa-fa-mo-ban-python-/