【JavaScript】LeetCode：71-75

71 搜索插入位置

• 二分查找
• 在最后一轮比较中，mid所指向的值 > target，right往左收，此时left所指向的位置为按顺序插入的位置；mid所指向的值 < target，left往右收，此时left所指向的位置为按顺序插入的位置。综上所述，如果最后未找到target，则返回left。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    let left = 0;
    let right = nums.length - 1;
    while(left <= right){
        let mid = Math.floor((left + right) / 2);
        if(nums[mid] > target){
            right = mid - 1;
        }else if(nums[mid] < target){
            left = mid + 1;
        }else{
            return mid;
        }
    }
    return left;
};

72 搜索二维矩阵

• 二分查找
• 展平数组：Array.flat()。
• 根据题意，把二维数组展平为一维数组后，该数组fmax为非严格递增序列，对fmax进行二分查找即可。

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function(matrix, target) {
    let fmax = matrix.flat();
    let left = 0;
    let right = fmax.length - 1;
    while(left <= right){
        let mid = Math.floor((left + right) / 2);
        if(fmax[mid] > target){
            right = mid - 1;
        }else if(fmax[mid] < target){
            left = mid + 1;
        }else{
            return true;
        }
    }
    return false;
};

73 在排序数组中查找元素的第一个和最后一个位置

• 二分查找
• 对数组进行两次二分查找，分别寻找target在数组中的第一个位置和最后一个位置。
• 第一个位置：当mid所指向的位置 < target时，left往右收；当mid所指向的位置 >= target时，right往左收。因此到最后一轮查找时，如果mid所指向的位置为target，left所指向的位置就是左端点，即第一个位置。
• 最后一个位置：当mid所指向的位置 > target时，right往左收；当mid所指向的位置 <= target时，left往右收。因此到最后一轮查找时，如果mid所指向的位置为target，right所指向的位置就是右端点，即最后一个位置。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function(nums, target) {
    let left = 0;
    let right = nums.length - 1;
    let lres = -2;
    let rres = -2;
    while(left <= right){
        let mid = Math.floor((left + right) / 2);
        if(nums[mid] > target){
            right = mid - 1;
        }else{
            left = mid + 1;
        }
    }
    rres = right;
    left = 0;
    right = nums.length - 1;
    while(left <= right){
        let mid = Math.floor((left + right) / 2);
        if(nums[mid] < target){
            left = mid + 1;
        }else{
            right = mid - 1;
        }
    }
    lres = left;
    if(lres != -2 && rres != -2 && (rres - lres >= 1 || rres - lres == 0)){
        return [lres, rres];
    }else{
        return [-1, -1];
    }
};

74 搜索旋转排序数组

• 二分查找
  
• 如上图所示，经过旋转的有序数组（[0, 1, 2, 4, 5, 6, 7]），可能会形成A（[4, 5, 6, 7]）、B（[0, 1, 2]）两个区域，B区域的数字均小于A区域。
• A区域左端点设为left，B区域右端点设为right，若mid所指向的数字 = target，则返回mid；否则分为以下两种情况。
• 当mid在A区域时：判断target是否在A区域的左半段之间（[left, mid]），如果存在，则将right往左收，否则将left往右收。
• 当mid在B区域时：判断target是否在B区域的右半段之间（[mid, right]），如果存在，则将left往右收，否则将right往左收。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    let left = 0;
    let right = nums.length - 1;
    while(left <= right){
        let mid = Math.floor((left + right) / 2);
        if(nums[mid] == target){
            return mid;
        }
        if(nums[mid] >= nums[left]){
            if(nums[left] <= target && target < nums[mid]){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }else{
            if(nums[mid] < target && target <= nums[right]){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
    }
    return -1;
};

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

• 二分查找
  
• 如上图所示，和上题相似，经过旋转的有序数组，可能会形成A、B两个区域，B区域的数字均小于A区域，因此最小值一定会出现在B区域。
• A区域左端点设为left，B区域右端点设为right，当left和right收缩到同一段递增的区间时，找到最小值min = left所指向的数字；否则分为以下两种情况。
• 当mid在A区域时：将left往右收。
• 当mid在B区域时：将right往左收，此时注意：right = mid，因为mid在可能出现最小值的的B区域，所以mid所指向的数字可能就是最小值。

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function(nums) {
    let left = 0;
    let right = nums.length - 1;
    while(left <= right){
        let mid = Math.floor((left + right) / 2);
        if(nums[left] <= nums[mid] && nums[mid] <= nums[right]){
            return nums[left];
        }else if(nums[mid] >= nums[left]){
            left = mid + 1;
        }else if(nums[mid] <= nums[right]){
            right = mid;
        }
    }
    return -1;
};