二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

leetcode链接：二分查找

分析

这道题目的前提是数组为有序数组，同时还强调，数组中无重复元素，因为一旦有重复元素，使用二分查找返回的元素下标可能不是唯一的。

所以使用二分法的前提条件：

有序，2. 数组中无重复值

二分法，掌握二分法的核心就是处理好二分法的边界条件，需要理解区间的定义。

写二分法，区间的定义一般分为两种：左闭右闭 [left,right] 或者左闭右开 [left,right).

两种区间的定义，分别有两种不同的二分写法

第一种写法，左闭右闭

第一种写法，定义 target 是在一个左闭右闭的区间里，也就是 [left,right]

区间的定义决定了二分法的边界，因为定义 target 在 [left,right]，所以有如下两点：

while(left <= right) ，要使用 <=, 因为闭区间包含 left 和 right，所以 left === right 是有意义的，要使用 <=
if(nums[middle] > target),这时 right 要赋值给 middle - 1, 因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1

来个图例，辅助理解，比如在 1，2，3，4，7，9，11 中查找 2。

代码如下

const search = function(nums, target) {
    let left = 0, right = nums.length - 1

    while(left <= right) { // 左闭右闭区间 [left, right]
        let mid = left + ((right - left)/2) // 防止溢出 等同于(left + right)/2
        // 如果 中间值比target 大，说明要查找的值，在左区间
        if (nums[mid] > target) {
            right = mid - 1   // [left, mid - 1]
        } else if (num[mid] < target) {
            // 说明要查找的值，在右区间
            left = mid + 1  // [mid - 1, right]
        } else {
            return mid
        }
    }
    return -1 // 未找到目标值时
};

第二种写法，左闭右开

第二种写法定义 target 在左闭右开的区间里，也就是 [left, right), 那这个边界处理和左闭右闭区间边界处理方式截然不同

while(left < right) 这里使用 < , 因为不包含 right ，所以 left === right 在 [left, right) 区间是没有意义的
if(nums[mid] > target), right 更新为middle，因为当前 nums[mid] 不等于 target，去左区间继续寻找，而寻找区间是左闭右开区间，所以 right 更新为 mid, 下一次查找区间不会去比较 nums[mid]

还是在 1，2，3，4，7，9，11 中查找 2。如图所示 （注意和方法一的区别）

代码


const search = function(nums, target) {
    let left = 0, right = nums.length

    while(left < right) {  // 左闭右开区间 [left, right)
        let mid = left + ((right - left)/2) // 防止溢出 等同于(left + right)/2
        // 如果 中间值比target 大，说明要查找的值，在左区间
        if (nums[mid] > target) {
            right = mid   // [left, mid]
        } else if (num[mid] < target) {
            // 说明要查找的值，在右区间
            left = mid   // [mid, right]
        } else {
            return mid
        }
    }
    return -1 // 未找到目标值时
};