J.A.R.V.I.S

life is not just live

二分查找及几种变形

二分查找

这个查找的要求是数组有序,我们要查找一个元素是不是存在于已排序数组中,先拿中间值与它比较,如果中间值比寻找值小则在中间值后面继续查找,否则在前面进行查找。

它的时间复杂度是o(logn)。所以它在查找时非常快,比如1024个数据他也就用10次就可以完成查找。

代码实现:

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;
}