二分搜索

# 二分搜索

# 搜索实现

function binarySearch(nums, target){
    var left = 0,
        right = nums.length - 1;

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

循环退出条件是left <= right，注意是<=

因为初始化 right 的赋值是 nums.length - 1，即最后一个元素的索引，而不是 nums.length。

我们这个算法中使用的是前者 [left, right] 两端都闭的区间。这个区间其实就是每次进行搜索的区间。

mid 的取值 Math.floor((low+high)/2) ?

二分法最大的特征, 就是一分为二, 再以中位数为坐标, 来确定选择左边还是右边

为什么 left = mid + 1，right = mid - 1？

刚才明确了「搜索区间」这个概念，而且本算法的搜索区间是两端都闭的，即 [left, right]。那么当我们发现索引 mid 不是要找的 target 时，下一步应该去搜索哪里呢？

当然是去搜索 [left, mid-1] 或者 [mid+1, right] 对不对？因为 mid 已经搜索过，应该从搜索区间中去除。

此算法的缺陷

比如说给你有序数组 nums = [1,2,2,2,3]，target 为 2，此算法返回的索引是 2，没错。但是如果我想得到 target 的左侧边界，即索引 1，或者我想得到 target 的右侧边界，即索引 3，这样的话此算法是无法处理的。

我们后续的算法就来讨论这两种二分查找的算法。

# 寻找左侧边界的二分搜索

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 剑指 Offer 53 - II. 0～n-1中缺失的数字

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14

left 指向 0，right 指向最后一个元素
计算中间坐标 mid：
- 如果mid = nums[mid]，说明[0, mid]范围内不缺失数字，left 更新为 mid + 1
- 如果mid < nums[mid]，说明[mid, right]范围内不缺失数字，right 更新为 mid - 1
检查 left 是否小于等于 mid，若成立，返回第 2 步；否则，向下执行
返回 left 即可

注意，根据题意，可以知道mid > nums[mid]这种情况不存在。

← 排序算法链表→