LeetCode 704 Binary Search

    
        标签：
        
            LeetCode
        
            二分搜索
        
    发布于：2020-06-07 11:22:13
    编辑于：2021-03-17 22:48:26
    浏览量：1456

无重复值的二分搜索

（升序 ascending order）

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int start = 0, end = nums.size()-1;
        while(start<=end){
            // Every loop we search [start, end], which means start and end could be the target.
            int i = start+(end-start)/2;
            if(nums[i]>target) {
                end = i-1;
            } else if(nums[i]==target){
                return i;
            } else if(nums[i]<target){
                start = i+1;
            }
        }
        return -1;
    }
};

采用两端都闭搜索区间，有以下几点要注意：

显然开始时 end 的值应在搜索区间内，因此其为 nums.size() -1。
while 的循环继续条件，因为我们采用两端都闭区间，因此当区间为空时条件才应该为 false，即区间非空时条件才应该为 true。
start 与 end 的更新，不应该更新为 nums[mid]，因为这个值不是 target 已被排除。

复杂度分析：while 循环体复杂度 O(1)

while 循环的个数？考虑到我们每次都削减了一半空间，即每次查找的区间大小为： n，n/2，n/4，…，n/(2^k)， k 即是循环的个数。

我们知道，最坏情况下区间只剩一个值的时候我们才发现目标值在或是不在区间内，因此令 n/(2^k) = 1，则：2^k = n，两边取 2 的对数，即 k = log n 则算法复杂度为 O(logN)

有重复值的二分搜索

寻找目标值的左侧边界

int left_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    // 搜索区间为 [left, right]
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            // 搜索区间变为 [mid+1, right]
            left = mid + 1;
        } else if (nums[mid] > target) {
            // 搜索区间变为 [left, mid-1]
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 收缩右侧边界
            right = mid - 1;
        }
    }
    // 检查出界情况
    if (left >= nums.length || nums[left] != target)
        return -1;
    return left;
}

寻找目标值的右侧边界

int right_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0, right = nums.length;
    while (left < right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            left = mid + 1; // 注意
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    return left - 1; // 注意
}

Links: LeetCode-704-Binary-Search