javaScript实现二分查找

发表于 | 分类于 | 阅读 次
字数统计: 188 | 阅读时长 ≈ 1

二分查找算法的前提是有序数组，查找数据和数组中间的元素相比较，相等就返回数组中间下标，如果不等于则取半继续查找。时间复杂度：O(log2 n )

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* 非递归写法 */
function binarySearch(arr, key) {
    let low = 0, high = arr.length - 1
    while (low <= high) {
        let mid = parseInt((low + high) / 2)
        if (key === arr[mid]) {
            return mid
        } else if (key > arr[mid]) {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
    return -1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* 递归写法 */
function binary_search(target, arr, low, high) {
    let start = low || 0
    let end = high || arr.length - 1
    if(start > end){
        return -1
    }
    let mid = parseInt((start + end) / 2)
    if (target === arr[mid]) {
        return mid
    } else if (target > arr[mid]) {
        return binary_search(target, arr, mid + 1, end)
    } else {
        return binary_search(target, arr, start, mid - 1)
    }
}