二分法

来自leetcode

704 二分查找

思路

1. 利用在右指针：设置target可选范围
2. 比较目标值 和 中间值 来缩小可选范围
3. 找到目标值 返回下标 没找到 返回 -1

本体较为简单，主要是二分的方法要知道，以及 可选区间的开闭

/*
 * @lc app=leetcode.cn id=704 lang=javascript
 *
 * [704] 二分查找
 */

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

35.搜索插入位置

四种情况

1. 目标值在数组所有元素之前
2. 目标值等于数组中某一个元素
3. 目标值插入数组中的位置
4. 目标值在数组所有元素之后

思路一

二分法 找目标值

• 找到就是按照二分查找的方法
• 没找到：插入元素
  • 在可选范围里面: 举例分析插在mid后面即可
  • 如果不在范围内 就两端位置

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {

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

思路二

重点代码注释

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    // 开始还是二分查找 缩小区间
    // 找得到目标就是索引
    // 找不到目标值 插入地方：与mid比较，最后位置肯定会取代mid
    // 当正好到< mid1 > mid2时，位置就确定好了  mid1
    // 注意ant初始值
    // 为什么初始值是nums.length:因为当target>nums[mid]一致都大于的时候，我们这里就直接放在末尾，也就是ant初始值
    let left = 0, right = nums.length - 1
    let ant = nums.length
    while(left <= right) {
        const mid = left + Math.floor((right - left) / 2)
        if(target > nums[mid]) left = mid + 1
        else if (target < nums[mid]) {
            ant = mid
            right = mid - 1
        }
        else return mid
    }
    return ant
};

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

关键在于分析一些细节

1. 左右边界分开查找使用二分
2. target的三种情况划分
3. 临界值的设置也很关键，为什么不是-1，而是-2
4. 我们这里的设置的边界值不包括target，为什么不包括

解析看代码注释

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
 // -1 -2 0 0 0 4 5 8
var searchRange = function(nums, target) {
    // 左右边界分开找 
    /**
    三种情况：1 target范围在最左边最右边 不存在目标值 返回[-1,-1] 
             2 target范围在中间    但不存在目标值 返回[-1,-1]
             3 target在范围里面且存在  返回 位置下标
     */
    /**
     我们这里的设置的边界值不包括target，为什么不包括？
     如果只有一个符合条件的时候，我们此时lB,rB也不会重合相等
     如果重合相等说明了没有目标值，也就是我们的情况二
     边界值初始值为什么不是-1？
     因为如果-1，在最左边是可能存在target的（[3,3,4,5] target = 3，此时lB = -1），所以我们设为-2
     */

    // 左边界： mid 位置 一直 >= target 最终，到临界值是就是左边界

    // (左边界)target ... target mid
    const getLeftBorder = function(nums, target) {
        let left = 0, right = nums.length -1, lB = -2
        while(left <= right) {
            let mid = left + Math.floor((right - left)/2)
            if(nums[mid] >= target) {
                right = mid - 1
                lB = right
            } else left = mid + 1
        }
        return lB
    }
    // 右边界： mid 位置 一直 <= target 最终，到临界值是就是右边界 
    // mid target ... target(右边界) 
    const getRightBorder = function(nums, target) {
        let left = 0, right = nums.length - 1, rB = -2
        while(left <= right) {
            let mid = left + Math.floor((right - left)/2)
            if(nums[mid] <= target) {
                left = mid + 1
                rB = left
            } else right = mid - 1
        }
        return rB
    }

    // 调用函数
    let lB = getLeftBorder(nums,target)
    let rB = getRightBorder(nums,target)
    // 情况一 目标值无 且在数组范围外
    if(lB ==  -2 || rB == -2) return [-1,-1]
    // 情况三 目标值右，且个数大于等于1   lB target ... target rB
    if(rB - lB > 1) return [lB + 1, rB - 1]
    // 情况二  目标值无，在数组范围内
    return [-1,-1]
};

总结二分法

1. 二分法的基本使用看706：二分查找即可
2. 使用条件：有序数组，无重复元素
3. 要在二分查找的过程中，保持不变量，就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作，这就是循环不变量规则。
4. 区间：左闭右闭即[left, right]，或者左闭右开即[left, right)
   • while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
   • while (left < right)，这里使用 < ,因为left == right在区间[left, right)是没有意义的
5. 操作: 设置一个中间值,与目标值对比,改变区间的边界,选择新的区间,循环