echo

任生命穿梭 时间的角落

0%

二分查找

在有序数组种,常用二分查找场景:寻找一个数、寻找左侧边界、寻找右侧边界。在二分查找算法的细节主要有两点:「while 循环中的的不等号是否带等号」,「边界的取值问题」。

二分查找框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int binarySearch(int[] nums, int target){
int left = 0, right = ...;
while(...){
int mid = left + (right - left) / 2;
if(nums[mid] == target){
...;
}else if(nums[mid] < target){
left = ...;
}else{
right = ...;
}
}
return ...;
}

mid = left + (right - left) / 2 是为了避免整数溢出,我们剩下的就是要在省略号的地方填上相应的步骤来实现二分查找。

寻找有序数组

在有序数组中寻找一个数,如果存在,返回下标,否则返回 -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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
package datastructure;

import java.util.Arrays;
import java.util.Random;

public class BinarySearch {
/*
* 在有序数组中寻找一个整数
* @param nums,有序数组
* @param target,需要寻找的目标
* @return 找到的数值索引,未找到返回 -1
* */
public static int binarySearchNum(int[] nums, int target) {
int left = 0, right = nums.length - 1; // 搜索区间为 [left, right]
while (left <= right) {//重点:因为左右闭区间,所以当 left == right 时,还有一个值需要判断,需要加上等号
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1; //搜索区间变成[mid + 1, right]
} else {
right = mid - 1; //因为右闭区间,搜索区间为[left, mid - 1]
}
}
return -1;
}

public static int binarySearchNum2(int[] nums, int target) {
int left = 0, right = nums.length; // 搜索区间为 [left, right)
while (left < right) { //左闭右开区间,当 left == right 时,区间内已经没有值
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;//搜索区间变成[mid + 1, right)
} else {
//因为右开区间,搜索区间为[left, mid),如果为 right = mid - 1,
//区间为[left, mid - 1),我们会漏掉 mid - 1位置的值
right = mid;
}
}
return -1;
}

public static void main(String[] args) {
int[] nums = new int[]{2,2,4,5,3,77,44,33,77,2,3,1,14,100};
Arrays.sort(nums);
System.out.println(Arrays.toString(nums));
for(int i = 0; i < 5; i++){
Random random = new Random(i*80);
int num = nums[random.nextInt(14)];
System.out.println("left <= right: searching " + num + " index: " + binarySearchNum(nums,num));
System.out.println("left < right: searching " + num + " index: " + binarySearchNum2(nums,num));
}
}
}

输出

1
2
3
4
5
6
7
8
9
10
11
[1, 2, 2, 2, 3, 3, 4, 5, 14, 33, 44, 77, 77, 100]
left <= right: searching 77 index: 12
left < right: searching 77 index: 11
left <= right: searching 3 index: 4
left < right: searching 3 index: 5
left <= right: searching 100 index: 13
left < right: searching 100 index: 13
left <= right: searching 3 index: 4
left < right: searching 3 index: 5
left <= right: searching 1 index: 0
left < right: searching 1 index: 0

num[mid] == target 时,我们已经找到了一个值的下标,直接返回即可。

关于 left <= right 和 left < right

  • 当初始化 left = 0, right = nums.length - 1 时,搜索区间为[left, right],当 left == right时,搜索区间内还有一个值 nums[left] 没有判断,循环条件内使用 left <= right,如果使用 left < right 最后需要加一次判断 nums[left] == target ?

  • 当初始化 left = 0, right = nums.length 时,搜索区间为[left, right),当 left == right时,搜索区间内没有值,循环条件内使用 left < right。

关于left、right 取值问题

  • 当初始化 left = 0, right = nums.length - 1 时,搜索区间为[left, right]mid = (left + right) / 2,如果nums[mid] < target,那么 target 值在 mid 右侧,left = mid + 1,此时搜索区间为[mid + 1,right],如果nums[mid] > target,那么 target 值在 mid 左侧,right = mid - 1,此时搜索区间为[left, mid - 1]

  • 当初始化 left = 0, right = nums.length 时,搜索区间为[left, right)mid = (left + right) / 2,如果nums[mid] < target,那么 target 值在 mid 右侧,left = mid + 1,此时搜索区间为[mid + 1,right),如果nums[mid] > target,那么 target 值在 mid 左侧,right = mid,此时搜索区间为[left, mid),如果right =mid - 1,那么搜索区间为[left, mid - 1),mid - 1 位置的值就不在搜索区间内,这是不对的,会造成错误。

寻找左侧边界

二分查找数组中从左至右等于 target 的第一个值的下标,没有则返回 -1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static int binarySearchLeftBoundNum(int[] nums, int target) {
int left = 0, right = nums.length; // 搜索区间为 [left, right)
while (left < right) { //左闭右开区间,当 left == right 时,区间内已经没有值
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
right = mid;//右侧逼近,下一个搜索区间[left, mid)
} else if (nums[mid] < target) {
left = mid + 1;//搜索区间变成[mid + 1, right]
} else {
//因为右开区间,搜索区间为[left, mid),如果为 right = mid - 1,
//区间为[left, mid - 1),我们会漏掉 mid - 1位置的值
right = mid;
}
}
//目前的 nums[left]是从左至右第一个大于等于 target 的值
if(left == nums.length){//target 大于所有值
return -1;
}else{
return nums[left] == target ? left : -1;
}
}

输出

1
2
3
4
[1, 2, 2, 2, 3, 3, 4, 5, 14, 33, 44, 77, 77, 100]
searching left bound 2 index: 1
searching left bound 77 index: 11
searching left bound 1 index: 0

在找到 target 时,没有立刻返回,而是缩小搜索区间的右侧,从右侧逼近,达到锁定左侧边界的目的。

寻找右侧边界

二分查找数组中从右至左等于 target 的第一个值的下标,没有则返回 -1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static int binarySearchRightBoundNum(int[] nums, int target) {
int left = 0, right = nums.length; // 搜索区间为 [left, right)
while (left < right) { //左闭右开区间,当 left == right 时,区间内已经没有值
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
left = mid + 1;//左侧逼近,下一个搜索区间[mid + 1, right)
} else if (nums[mid] < target) {
left = mid + 1;//搜索区间变成[mid + 1, right]
} else {
//因为右开区间,搜索区间为[left, mid),如果为 right = mid - 1,
//区间为[left, mid - 1),我们会漏掉 mid - 1位置的值
right = mid;
}
}

// 目前的 nums[left] 左边的部分的值都是大于等于 target
if(left == 0){//target 小于所有值
return -1;
}else{
//返回最后一个等于 target 值的下标
return nums[left - 1] == target ? left - 1 : -1;
}
}

输出

1
2
3
4
[1, 2, 2, 2, 3, 3, 4, 5, 14, 33, 44, 77, 77, 100]
searching right bound 2 index: 3
searching right bound 77 index: 12
searching right bound 1 index: 0

在找到 target 时,没有立刻返回,而是缩小搜索区间的左侧,从左侧逼近,达到锁定右侧边界的目的。

Powered By Valine
v1.5.2