折半查找法也称为二分查找法,它充分利用了元素间的次序关系,采用分治策略,可在最坏的情况下用O(log n)完成搜索任务。
但是边界问题需要严谨确定,否则陷入死循环或者找不到应有对象。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int find(int[] array, int value) {
int found = -1;
int start = 0;
int end = array.length - 1; // 下标范围是数目减去一
int mid;
int o=1;
while (start <= end) { // 必须是闭合区间,否则当两者差一的时候会陷入死循环
mid = (start + end) / 2;
if (array[mid] == value) {
return mid;
} else if (array[mid] < value) {
start = mid + 1;
} else if (array[mid] > value) {
end = mid - 1;
}
o++;
}
return found;
}