二分查找梳理

二分查找梳理

使用前提:满足单调性.

最基础常用的版本

int left = 0;
int right = n-1;
while(left<=right)
{
    int mid = (left+right)>>1;//这样可以正确地处理负数
    if(arr[mid]<k)
    {
        left = mid+1;
    }
    else if(arr[mid]>k)
    {
        right = mid-1;
    }
    else
    return mid;
}
//如果没有搜索到,那么走到这时候l和r的值是这个元素在应该插入到该有序数组到位置.(leetCode 35)

这里的处理思想很简单,就是纯粹的闭区间[left,right].如果k在mid右边,那么就从[mid+1,right]开始找(由于mid肯定不是答案,那么就从mid+1开始找). 这是最最常用的.适合找到的数是唯一解的情况.

半开半闭区间的写法

最典型的用法就是LeetCode 34 在排序数组查找元素的第一个和最后一个位置

题目的大意其实是:如果有1111111112222222222233333333这样的数组,如何找到第一个2和最后一个2的位置?

原题:

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

解答:

vector<int> searchRange(vector<int>& nums, int target) 
    {
        if(nums.size()==0)return {-1,-1};
        int l = 0,r = nums.size()-1;
    //找左边第一个 可能的答案区间是[l,r)
        while(l<r)
        {
            int mid = (l+r)>>1;
            if(nums[mid]>=target)r = mid;
            else l = mid+1;
        }
        int leftPos = l;
        if(nums[l]!=target)return {-1,-1};
        l = 0,r = nums.size()-1;
    //找右边的第一个 可能的答案区间是(l,r]
        while(l<r)
        {
            int mid = (l+r+1)>>1;
            if(nums[mid]<=target)l = mid;
            else r = mid - 1;
        }
        if(nums[l]!=target)return {-1,-1};
        return {leftPos,l};
    }

模板的记忆: - 如果在 if(check(mid))后面接的是l,那么int mid时就需要+1.check(mid)往往取的是等号. - 在else之后,要么+1,要么-1.原因同最基础常用的版本。 - 写完之后思考一下,如果mid落到中间的2中,按照逻辑答案区间是包括左边还是包括右边. - 最后l和r是一定相等的.