思路

  1. 从数组的中间元素开始,如果中间元素正好是目标值,则搜索结束。
  2. 如果目标值大于小于中间元素,则在大于小于中间元素的那一半数组中二分搜索

二分搜索前提:数组有序

时间复杂度:O(logN)

实现

现有有序数组[3, 4, 5, 6, 7, 9, 12, 15],进行二分搜索12

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Array.prototype.binarySearch = function (item) {
let low = 0;
let high = this.length - 1;
while (low <= high) {
const mid = Math.floor((low + high) / 2);
const element = this[mid];
if (element > item) {
high = mid - 1;
} else if (element < item) {
low = mid + 1;
} else {
return mid;
}
}
return -1;
};

const res = [3, 4, 5, 6, 7, 9, 12, 15].binarySearch(12);
console.log(res);

执行结果: