二分查找

首发于：2020-08-13

二分查找（Binary Search）算法，也叫折半查找算法。二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。

时间复杂度O(logn)

最简单的二分查找

数据必须是有序的，且不存在重复项。

/**
 * 二分查找，最简单的情况
 * 数组必须有序，不存在重复
 * @param {array} arr 待排序数组
 * @param {number} target 目标数据 
 */
function BinarySearch(arr, target) {
    if (arr.length <= 1) return -1
    // 低位下标
    let lowIndex = 0
    // 高位下标
    let highIndex = arr.length - 1

    while (lowIndex <= highIndex) {
        // 中间下标
        const midIndex = Math.floor((lowIndex + highIndex) / 2)
        if (target < arr[midIndex]) {
            highIndex = midIndex - 1
        } else if (target > arr[midIndex]) {
            lowIndex = midIndex + 1
        } else {
            // target === arr[midIndex]
            return midIndex
        }
    }
    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))

变体一：查找第一个值等于给定值的元素

有序数据集合中存在重复的数据。

/**
 * 二分查找，查找第一个值等于给定值的元素
 * 数组必须有序，存在重复
 * @param {array} arr 待排序数组
 * @param {number} target 目标数据 
 */
function BinarySearchFirst(arr, target) {
    if (arr.length <= 1) return -1
    // 低位下标
    let lowIndex = 0
    // 高位下标
    let highIndex = arr.length - 1

    while (lowIndex <= highIndex) {
        // 中间下标
        const midIndex = Math.floor((lowIndex + highIndex) / 2)
        if (target < arr[midIndex]) {
            highIndex = midIndex - 1
        } else if (target > arr[midIndex]) {
            lowIndex = midIndex + 1
        } else {
            // 当 target 与 arr[midIndex] 相等的时候，如果 midIndex 为0或者前一个数比 target 小那么就找到了第一个等于给定值的元素，直接返回
            if (midIndex === 0 || arr[midIndex - 1] < target) return midIndex
            // 否则高位下标为中间下标减1，继续查找
            highIndex = midIndex - 1
        }
    }
    return -1
}

// 下面为测试用
const arr = [1, 4, 5, 6, 7, 8, 11, 11, 11, 42, 44, 54, 56, 77, 102]
console.log(BinarySearchFirst(arr, 11))
console.log(BinarySearchFirst(arr, 44))
console.log(BinarySearchFirst(arr, 1))
console.log(BinarySearchFirst(arr, 102))
console.log(BinarySearchFirst(arr, 1111))

变体二：查找最后一个值等于给定值的元素

有序数据集合中存在重复的数据。

/**
 * 二分查找，查找最后一个值等于给定值的元素
 * 数组必须有序，存在重复
 * @param {array} arr 待排序数组
 * @param {number} target 目标数据 
 */
function BinarySearchLast(arr, target) {
    if (arr.length <= 1) return -1
    // 低位下标
    let lowIndex = 0
    // 高位下标
    let highIndex = arr.length - 1

    while (lowIndex <= highIndex) {
        // 中间下标
        const midIndex = Math.floor((lowIndex + highIndex) / 2)
        if (target < arr[midIndex]) {
            highIndex = midIndex - 1
        } else if (target > arr[midIndex]) {
            lowIndex = midIndex + 1
        } else {
            // 当 target 与 arr[midIndex] 相等的时候，如果 midIndex 为0或者后一个数不等于 target 那么就找到了最后一个等于给定值的元素，直接返回
            // 这里不能取a rr[midIndex + 1] > target 可能会存在边界问题
            if (midIndex === 0 || arr[midIndex + 1] !== target) return midIndex
            // 否则低位下标为中间下标加1，继续查找
            lowIndex = midIndex + 1
        }
    }
    return -1
}

// 下面为测试用
const arr = [1, 4, 5, 6, 7, 8, 11, 11, 11, 42, 44, 54, 56, 77, 102]
console.log(BinarySearchLast(arr, 11))
console.log(BinarySearchLast(arr, 44))
console.log(BinarySearchLast(arr, 1))
console.log(BinarySearchLast(arr, 102))
console.log(BinarySearchLast(arr, 1111))

变体三：查找第一个大于等于给定值的元素

有序数据集合中存在重复的数据。

/**
 * 二分查找，查找第一个大于等于给定值的元素
 * 数组必须有序，存在重复
 * @param {array} arr 待排序数组
 * @param {number} target 目标数据 
 */
function BinarySearchFirstBig(arr, target) {
    if (arr.length <= 1) return -1
    // 低位下标
    let lowIndex = 0
    // 高位下标
    let highIndex = arr.length - 1

    while (lowIndex <= highIndex) {
        // 中间下标
        const midIndex = Math.floor((lowIndex + highIndex) / 2)
        if (arr[midIndex] >= target) {
            // 如果 midIndex 为0或者前一个数小于 target 那么找到第一个大于等于给定值的元素，直接返回
            if (midIndex === 0 || arr[midIndex - 1] < target) return midIndex
            // 否则高位下标为中位下标减1
            highIndex = midIndex - 1
        } else {
            lowIndex = midIndex + 1
        }
    }
    return -1
}

// 下面为测试用
const arr = [1, 4, 5, 6, 7, 8, 11, 11, 11, 42, 44, 54, 56, 77, 102]
console.log(BinarySearchFirstBig(arr, 10))
console.log(BinarySearchFirstBig(arr, 44))
console.log(BinarySearchFirstBig(arr, 1))
console.log(BinarySearchFirstBig(arr, 102))
console.log(BinarySearchFirstBig(arr, 1111))

变体四：查找最后一个小于等于给定值的元素

有序数据集合中存在重复的数据。

/**
 * 二分查找，查找最后一个小于等于给定值的元素
 * 数组必须有序，存在重复
 * @param {array} arr 待排序数组
 * @param {number} target 目标数据 
 */
function BinarySearchLastSmall(arr, target) {
    if (arr.length <= 1) return -1
    // 低位下标
    let lowIndex = 0
    // 高位下标
    let highIndex = arr.length - 1

    while (lowIndex <= highIndex) {
        // 中间下标
        const midIndex = Math.floor((lowIndex + highIndex) / 2)
        if (arr[midIndex] <= target) {
            // 如果 midIndex 最后一个或者后一个数大于 target 那么找到最后一个小于等于给定值的元素，直接返回
            if (midIndex === arr.length - 1 || arr[midIndex + 1] > target) return midIndex
            // 否则低位下标为中位下标加1
            lowIndex = midIndex + 1
        } else {
            highIndex = midIndex - 1
        }
    }
    return -1
}

// 下面为测试用
const arr = [1, 4, 5, 6, 7, 8, 11, 11, 11, 42, 44, 54, 56, 77, 102]
console.log(BinarySearchLastSmall(arr, 12))
console.log(BinarySearchLastSmall(arr, 44))
console.log(BinarySearchLastSmall(arr, 1))
console.log(BinarySearchLastSmall(arr, 102))
console.log(BinarySearchLastSmall(arr, 1111))