二分查找 - 变形

来源：基础算法精讲 by 灵茶山艾府

题目	代码	备注
162. 寻找峰值	代码
153. 寻找旋转排序数组中的最小值	代码
33. 搜索旋转排序数组	代码	两种方法
74. 搜索二维矩阵	代码	*课后作业
1901. 寻找峰值 II	代码	*课后作业
154. 寻找旋转排序数组中的最小值 II	代码	*课后作业

例题

162. 寻找峰值

题目链接：在相邻元素互不相同的数组中，返回任意一个严格大于左右相邻值的元素下标。

示例：输入 nums = [1,2,3,1]，输出 2。

这个题不能排序，但是却可以用二分，因为题目说如果有多个峰值随便找到一个就可以，而且相邻元素不会相同

/**
 * @param {number[]} nums
 * @return {number}
 */
var findPeakElement = function (nums) {
    //相邻的数都不同，假设，随便找一个，
    //样例模拟发现，如果r初始化在n-1，答案就小于等于nums[r]，答案大于[l]；；二分是大于l小于r
    let l = -1, n = nums.length;
    let r = n - 1;
    while (l + 1 < r) {
        let mid = Math.floor((l + r) / 2);
        if (nums[mid] < nums[mid + 1]) {
            //ans may be in right;
            l = mid;
        }
        else r = mid
        // console.log(mid,l,r)
    }
    return r;

};

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

题目链接：在元素互不相同的旋转升序数组中找出最小值。

示例：输入 nums = [3,4,5,1,2]，输出 1。

利用好有序这一性质，看成一个递增的线段，旋转就看成线段分成两部分重排序，有点像跳跃间断点？

var findMin = function(nums) {
    //利用好事先有序的特性，按照视频里的线段来可视化的分析中间值跟tail值大小情况
    let l = -1, n = nums.length;
    let r = n - 1;
    while (l + 1 < r) {
        let mid = Math.floor((l + r) / 2);
        if (nums[mid] > nums[n-1]) {
            l = mid;
        }
        else r = mid
        // console.log(mid,l,r)
    }
    return nums[r];
};

33. 搜索旋转排序数组

题目链接：在元素互不相同的旋转升序数组中查找 target，返回下标或 -1。

示例：输入 nums = [4,5,6,7,0,1,2], target = 0，输出 4。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */


var search = function (nums, target) {
    let n = nums.length;
    const tail = nums[n-1];
    let minIndex = findMin(nums);

    if(target > tail){
        return lowerBound(nums,-1,minIndex,target);
    }

    return lowerBound(nums,minIndex - 1,n,target);
};
// 153. 寻找旋转排序数组中的最小值（返回的是下标）
var findMin = function (nums) {
    let left = -1, right = nums.length - 1; // 开区间 (-1, n-1)
    while (left + 1 < right) { // 开区间不为空
        const mid = Math.floor((left + right) / 2);
        if (nums[mid] < nums[nums.length - 1]) {
            right = mid;
        } else {
            left = mid;
        }
    }
    return right;
};

var lowerBound = function (nums, left, right, target) {
    while (left + 1 < right) { // 开区间不为空
        // 循环不变量：
        // nums[right] >= target
        // nums[left] < target
        const mid = Math.floor((left + right) / 2);
        if (nums[mid] >= target) {
            right = mid; // 范围缩小到 (left, mid)
        } else {
            left = mid; // 范围缩小到 (mid, right)
        }
    }
    return nums[right] === target ? right : -1;
};