刘文柱

# 二分搜索

# 二分搜索的思路

  • 从数组的中间元素开始，如果中间元素正好是目标值，则搜索结束。

  • 如果目标值大于或者小于中间元素，则在大于或小于中间元素的那一半数组中搜素。

# JS实现

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

# 二分搜索的时间复杂度

  • 每次比较都使搜索范围缩小一半。

  • 时间复杂度 O(logN)

← 练习 →