二分查找

二分查找(BinarySearch)

// 数组必须有序 不存在重复
const BinarySearch = (sortedArr, target) => {
    if (sortedArr.length === 0) return -1
    let low = 0
    let high = sortedArr.length - 1
    while (low <= high) {
        const mid = Math.floor((low + high) / 2)
        if (target === sortedArr[mid]) {
            return mid
        } else if (target < sortedArr[mid]) {
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return -1
}
const arr = [1, 4, 5, 6, 7, 8, 10, 11, 23, 42, 44, 54, 56, 77, 102]
console.log(BinarySearch(arr, 44))
console.log(BinarySearch(arr, 1))
console.log(BinarySearch(arr, 102))
console.log(BinarySearch(arr, 1111))

注意循环退出条件是 low <= high
注意 high = mid - 1,low = mid + 1,没这个 1 可能会死循环(high=low时)
(low + high) / 2 可优化为 low + (high - low) / 2,防止high+low溢出
必须是顺序表结构(数组),必须是有序数据
理论上二分查找可以解决的问题,散列表 二叉树都能解决,但是需要更多额外空间
所以限制内存空间及 数据量较大时 使用 二分查找

查找k次,2的k次方能覆盖n个元素
时间复杂度O(logn)

查找第一个等于给定值

const binaryFindFirst = (sortedArr, target) => {
    if (sortedArr.length === 0) return -1
    let low = 0
    let high = sortedArr.length - 1
    while (low <= high) {
        const mid = Math.floor((low + high) / 2)

        if (target < sortedArr[mid]) {
            high = mid - 1
        } else if (target > sortedArr[mid]) {
            low = mid + 1
        } else {
            if (mid === 0 || sortedArr[mid - 1] < target) return mid
            high = mid - 1
        }
    }
    return -1
}
const arr = [1, 2, 3, 4, 4, 4, 4, 4, 6, 7, 8, 8, 9]
const first = binaryFindFirst(arr, 4)
console.log(`FindFirst: ${first}`)

查找最后一个相等的数

const binaryFindLast = (sortedArr, target) => {
    if (sortedArr.length === 0) return -1
    let low = 0
    let high = sortedArr.length - 1
    while (low <= high) {
        const mid = Math.floor((low + high) / 2)
        if (target < sortedArr[mid]) {
            high = mid - 1
        } else if (target > sortedArr[mid]) {
            low = mid + 1
        } else {
            if (mid === sortedArr.length - 1 || sortedArr[mid + 1] > target) return mid
            low = mid + 1
        }
    }
    return -1
}
const arr = [1, 2, 3, 4, 4, 4, 4, 4, 6, 7, 8, 8, 9]
const last = binaryFindLast(arr, 4)
console.log(`FindLast: ${last}`)

查找第一个大于等于给定值的元素

const binaryFindFistBig = (sortedArr, target) => {
    if (sortedArr.length === 0) return -1
    let low = 0
    let high = sortedArr.length - 1
    while (low <= high) {
        const mid = Math.floor((low + high) / 2)
        if (target <= sortedArr[mid]) {
            if (mid === 0 || sortedArr[mid - 1] < target) return mid
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return -1
}
const arr = [1, 2, 3, 4, 4, 4, 4, 4, 6, 7, 8, 8, 9]
const FirstBig = binaryFindFistBig(arr, 5)
console.log(`FindFirstBig: ${FirstBig}`)

查找最后一个小于等于给定值的元素

const binaryFindLastSmall = (sortedArr, target) => {
    if (sortedArr.length === 0) return -1
    let low = 0
    let high = sortedArr.length - 1
    while (low <= high) {
        const mid = Math.floor((low + high) / 2)
        if (target < sortedArr[mid]) {
            high = mid - 1
        } else {
            if (mid === sortedArr.length - 1 || sortedArr[mid + 1] >= target) return mid
            low = mid + 1
        }
    }
    return -1
}

const arr = [1, 2, 3, 4, 4, 4, 4, 4, 6, 7, 8, 8, 9]
const LastSmall = binaryFindLastSmall(arr, 4)
console.log(`FindLastSmall: ${LastSmall}`)