而分查找又叫折半查找,原理很简单:对有序数组先取中间值,对比大小,大于中间值则取后半部分(增加部分)的中间值,继续折半查找,类似于:猜数字游戏,前提是数组要有序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var nums = [1, 14, 2, 22, 22, 23, 29, 30, 5, 75, 76];

function binSearch(arr, data) {
var upperBound = arr.length-1;
var lowerBound = 0;
while (lowerBound <= upperBound) {
var mid = Math.floor((upperBound + lowerBound) / 2);
if (arr[mid] < data) {
lowerBound = mid + 1;
}else if (arr[mid] > data) {
upperBound = mid - 1;
}else {
return mid;
}
}
return -1;
}

binSearch(nums,22); // 3