算法【二分搜索篇】

[SampsonKY]

二分搜索框架

function binarySearch(nums, target){
    let left = 0, right = nums.length-1
    // 区间 [left, right]
    while(left<=right){
        let mid = left + (right - left)/2
        if(nums[mid] === target){
            ...
        } else if(nums[mid] < target){
            left = ...
        } else if(nums[mid] > target){
            right ...
        }
    }
    return ...
}

• 代码中 left + (right - left) / 2 就和 (left + right) / 2 的结果相同，但是有效防止了 left 和 right 太大直接相加导致溢出。
• 建议使用 else if 把所有情况写清楚

寻找一个数

function binarySearch(nums, target){
    let left = 0, right = nums.length-1
    while(left<=right){
        let mid = left + Math.floor((right + left)/2)
        if(nums[mid] === target){
            return mid
        } else if(nums[mid] < target){
            left = mid+1
        } else if(nums[mid] > target){
            right = mid-1
        }
    }
    return -1
}

寻找左侧边界的二分搜索

示例：

输入：
[1,2,2,2,3] 2
输出：1

代码：

function left_bound(nums, target){
    let left = 0, right = nums.length-1
    // 搜索区间 [left, right]
    while(left<=right){
        let mid = Math.floor((right + left)/2)
        // 收缩右边界
        if(nums[mid] === target){
            right = mid-1
        } else if(nums[mid] < target){
            left = mid+1 //搜索区间 [mid+1, right]
        } else if(nums[mid] > target){
            right = mid-1 //搜索区间 [left, mid-1]
        }
    }
    if(left >= nums.length || nums[left] !== target) return -1
    return left
}

寻找右侧边界的二分搜索

示例：

输入：
[1,2,2,2,3] 2
输出：3

代码：

function left_bound(nums, target){
    let left = 0, right = nums.length-1
    // 搜索区间 [left, right]
    while(left<=right){
        let mid = Math.floor((right + left)/2)
        // 收缩左边界
        if(nums[mid] === target){
            left = mid+1
        } else if(nums[mid] < target){
            left = mid+1 //搜索区间 [mid+1, right]
        } else if(nums[mid] > target){
            right = mid-1 //搜索区间 [left, mid-1]
        }
    }
    // 检查right越界的情况
    if(right<0 || nums[right] !== target) return -1
    return right
}

leetcode 题目

• No.69 x 的平方根

• No.744 寻找比目标字母大的最小字母

• No.540 有序数组中的单一元素

• No.278 第一个错误版本

• No.153 寻找旋转数组中的最小值