二分查找技巧｜刷题合集

剑指 Offer 04. 二维数组中的查找

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var findNumberIn2DArray = function(matrix, target) {
    if(matrix.length===0) return false;
    let m=matrix.length;
    let n=matrix[0].length;
    let left,right;
    //从右上角开始找，采用双指针,比它大的下移，小的左移
    left=0,right=n-1;
    while(left<m && right>=0){
        if(matrix[left][right]<target){
            left++;
        }
        else if(matrix[left][right]>target){
            right--;
        }
        else return true;

    }
    return false;

};

704. 二分查找

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    let left=0;
    let right=nums.length-1;//注意边界的判断。第length-1位。 故while要判断<=,比如避免漏掉[2,2]的判断，即left=right.
    while(left<=right){
        let mid=left +Math.floor((right-left)/2);
        if(nums[mid]===target){
            return mid
        }
        else if(nums[mid]<target){//搜索区间为[left,right]
            left=mid+1;
        }
        else if(nums[mid]>target){
            right=mid-1;
        }
    }
    return -1;



}

剑指 Offer 11. 旋转数组的最小数字

153. 寻找旋转排序数组中的最小值

/**
 * @param {number[]} numbers
 * @return {number}
 */
var minArray = function(numbers) {
    let left=0;
    let right=numbers.length-1;
    while(left<=right){//找左数组。还是右数组，右数组所有值小于左数组
        let mid=left+Math.floor((right-left)/2);
        if(numbers[mid]<numbers[right]){//在左数组
            right=mid;//若mid恰好为最小的值
        }
        else if(numbers[mid]>numbers[right]){//最小值在右数组
            left=mid+1;
        }
        else {//相等则缩小范围
        right=right-1;

        }

    }
    return numbers[left];
};