算法图解：二分查找
截图来自《算法图解》这本书
![]()
![]()
![]()
![]()
![]()
![]()
![]()
练习代码：
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
|
public static boolean searchBoo(Integer[] ints, Integer low, Integer height,Integer need) {
if (low > height){
return false;
}
int mid = low + (high - low) / 2;
if (ints[mid].equals(need)) {
return true;
}else if (ints[mid] > need) {
return searchBoo(ints, low, mid -1, need);
} else if (ints[mid] < need) {
return searchBoo(ints, mid + 1, height, need);
}else {
return false;
}
}
public static int searchindex(Integer[] ints, Integer low, Integer height,Integer need) {
if (low > height){
return -1;
}
int mid = low + (high - low) / 2;
if (ints[mid].equals(need)) {
return mid;
}else if (ints[mid] > need) {
return searchindex(ints, low, mid -1, need);
} else if (ints[mid] < need) {
return searchindex(ints, mid + 1, height, need);
}
return mid;
}
|
这是一个经典的话题，如何计算二分查找中的中值？大家一般给出了两种计算方法：
- 算法一：
mid = (low + high) / 2
- 算法二：
mid = low + (high – low)/2
乍看起来，算法一简洁，算法二提取之后，跟算法一没有什么区别。但是实际上，区别是存在的。算法一的做法，在极端情况下，(low + high)存在着溢出的风险，进而得到错误的mid结果，导致程序错误。而算法二能够保证计算出来的mid，一定大于low，小于high，不存在溢出的问题。
二分查找法的缺陷
二分查找法的O(log n)让它成为十分高效的算法。不过它的缺陷却也是那么明显的。就在它的限定之上：必须有序，我们很难保证我们的数组都是有序的。当然可以在构建数组的时候进行排序，可是又落到了第二个瓶颈上：它必须是数组。
数组读取效率是O(1)，可是它的插入和删除某个元素的效率却是O(n)。因而导致构建有序数组变成低效的事情。
解决这些缺陷问题更好的方法应该是使用二叉查找树了，最好自然是自平衡二叉查找树了，既能高效的（O(n log n)）构建有序元素集合，又能如同二分查找法一样快速（O(log n)）的搜寻目标数。
