二分查找
前置要求：数组有序
时间复杂度：log(n)
几种常见的问题：
- 数组中查找target
- 数组中有重复，查找第一个target
- 数组中有重复，查找最后一个target
- 查找等于target或第一个小于target的值
- 查找等于target或第一个大于target的值
代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
public int binarySearch(int[] a, int value) {
int n = a.length;
int start = 0, end = n - 1;
//这个地方是 <=
while (start <= end) {
//取中间值，这个方法可能会溢出，可以采用下面的方法
// int mid = (start + end) / 2;
int mid = start + (end - start) / 2;
//更进一步，也可以使用位运算
// int mid = start + ((start + end) >> 1);
if (a[mid] == value) {
return mid;
} else if (a[mid] > value) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return -1;
}
|
再给出一个递归实现的二分查找方法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
public int binarySearchDeep(int[] a, int value) {
int n = a.length;
return binarySearchDeepHelp(a, 0, n - 1, value);
}
private int binarySearchDeepHelp(int[] a, int low, int high, int value) {
if (low > high) {
return -1;
}
int mid = low + ((high - low) >> 1);
if (a[mid] == value) {
return mid;
} else if (a[mid] < value) {
return binarySearchDeepHelp(a, mid + 1, high, value);
} else {
return binarySearchDeepHelp(a, low, mid - 1, value);
}
}
|
代码中有一个地方，我们取中间下标时，最基本的方法是mid=(low+higt)/2。但这个时候可能会造成溢出，所以我们可以采用mid=low+(high-low)。如果需要继续优化可以使用位运算mid=low+((high-low)>>1)。
局限性
-
排序
这个毋容置疑，不排好序，我们取中间值比较是没有意义的
-
数组
二分查找需要按照下标随机访问元素，数组访问的时间复杂度是o(1)，而链表是o(n)。所以二分查找不使用与链表。
-
数据量太大时
因为需要数组这种数据结构，而数组在内存中需要连续存储。当数据量太大，比如1gb大小，那么就需要1gb的连续内存区间，所以当数据量太大时会比较吃力。
习题
用二分查找实现，求一个数的平方根，要求精确到小数点后6位。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
public double mySqrt(double x) {
double low = 0.0, high = x;
double mid = low + (high - low) / 2.0;
//表示 10（^-6^）即小数点后6位
double eps = 1e-6;
while (Math.abs(high - low) > eps) {
// 首先找到中间值
mid = low + (high - low) / 2;
double temp = mid * mid;
// 比较并更新 high和low
if ((temp - x) > eps) {
high = mid;
} else if ((temp - x) < -eps) {
low = mid;
} else {
return mid;
}
}
return mid;
}
|
变形一
查找第一个值等于给定值的元素
现在有这样一个数组，[1,2,3,3,3,4,5]，要求查找3。对数组里面三个3分别命名为3a,3b,3c。按照上面二分查找方法，返回的3是3b。我们现在要求返回第一个也就是3a。
这时上面的代码就无法处理这种情况了。我们针对这个变形来实现一下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
public int binarySearch1(int[] a, int value) {
int n = a.length;
int low = 0, high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] > value) {
high = mid - 1;
} else if (a[mid] < value) {
low = mid + 1;
} else {
// 主要在这个地方
//如果这个元素已经是数组的第一个元素了，那么就直接返回
//如果不是，则判断上一个元素的值是不是等于value，如果不是则返回
//如果是则更新high ，high=mid-1
if ((mid == 0) || (a[mid - 1] != value)) {
return mid;
} else {
high = mid - 1;
}
}
}
return -1;
}
|
变形二
查找最后一个值等于给定值的元素
在变形一种，我们查找第一个给定值的元素，我们这次查找最后一个给定值的元素。
代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
public int binarySearchLastMatch(int[] a, int value) {
int n = a.length;
int high = n - 1, low = 0;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] >= value) {
if ((mid == 0) || (a[mid - 1] < value)) {
return mid;
} else {
high = mid - 1;
}
} else {
low = mid + 1;
}
}
return -1;
}
|
变形三
查找第一个大于等于给定值的元素
给定数组，给定值，如果值存在则返回第一个元素的下标，否则返回第一个大于给定值的元素下标。
我们以这个数组为例：[1,2,4,4,5,6]。我们如果查找4，它需要返回2，即满足条件的第一个元素下标。我们如果查找3，它也需要返回2，因为3不存在数组中，第一个大于给定值的元素就是4，下标为2。
代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
public int binarySearch3(int[] a, int value) {
int n = a.length;
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] >= value) {
if ((mid == 0) || (a[mid - 1] < value)) {
return mid;
} else {
high = mid - 1;
}
} else {
low = mid + 1;
}
}
return -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
|
/**
* 变形四，查找最后一个小于等于给定值的元素
* [3,5,6,6,8,9,10]。
* 当值存在时，返回最后一个等于给定值的元素
* 不存在时，返回最后一个小于给定值的元素
* 查询6，7都返回下标3
*
* @param a 数组
* @param value 要查找的值
* @return
*/
public int binarySearch4(int[] a, int value) {
int n = a.length;
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] > value) {
high = mid - 1;
} else {
if ((mid == n - 1) || (a[mid + 1] > value)) {
return mid;
} else {
low = mid + 1;
}
}
}
return -1;
}
|