二分查找小结

最基础的二分查找题目，在一个有序的数组当中查找某个数，如果找到，则返回这个数在数组中的下标，如果没有找到就返回- 1

function binarySearch(nums, target) {
    let left = 0; 
    let right = nums.length - 1;
    while(left <= right) { // 注意这里是 <=
        let mid = (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;
}

经典题目 875. 爱吃香蕉的珂珂

/**
 * @param {number[]} piles
 * @param {number} H
 * @return {number}
 */
var minEatingSpeed = function(piles, H) {
    // 速度为k的时候是否能把香蕉吃完
    const isPossible = function(piles, H, K) {
        let time = 0
        for (let i = 0; i < piles.length; i++) {
            time += Math.ceil(piles[i] / K) 
        }
        return time <= H
    }

    // 二分法查找最小速度
    let low = 1
    let heigh = Math.max(...piles) // 获取香蕉的最大值为最大速度，因为没堆香蕉吃1小时是最快的
    while (low < heigh) {
        let mid = Math.floor((low + heigh) / 2)
        if (!isPossible(piles, H, mid)) {
            low = mid + 1
        } else {
            heigh = mid
        } 
    }
    return low
};

在连续的空间线性搜索，这就是二分查找可以发挥作用的标志。