3.二分查找

/*
二分查找也被称为二分法或者折半查找，每次查找时通过将待查找区间分成两部分并只取一部分继续查找，将查找的复杂度大大减少，对于一个
长度为O(n)的数组，二分查找的时间复杂度为O(log n)
while(l<=r)  小于等于
*/


//69.x的平方根
/*
题目描述：给定一个非负整数，求它的开方，向下取整。
输入输出样例：输入一个整数，输出一个整数。
Input:8 Output:2   8的开方是2.82842...，向下取整即是2.
题解：我们可以把这道题想像成，给定一个非负整数a，求f(x)=x^2-a=0的解。因为我们只考虑x>=0，所以f(x)在定义域上是单调递增的。
考虑到f(0)=-a<=0,f(a)=a^2-a>=0,我们可以对[0,a]区间使用二分法找到f(x)=0的解。
注意，在以下代码里，为了防止除以0，我们把a=0的情况单独考虑，然后对区间[1,a]进行二分查找。我们使用了左闭右闭的写法。
*/
int mySqrt(int a){
    if(a==0) return a;
    int l=1,r=a,sqrt,mid;
    while(l<=r){
        mid=(l+r)/2;
        sqrt=a/mid;
        if(sqrt == mid){
            return mid;
        }else if(sqrt > mid){
            l=mid+1;
        }else{
            r=mid-1;
        }
    }
    return r;
}


//34.在排序数组中查找元素的第一个和最后一个位置
/*
给定一个增序的整数数组和一个值，查找该值第一次和最后一次出现的位置
输入是一个数组和一个值，输出是该值第一次出现的位置和最后一次出现的位置（从0开始）；如果不存在该值，则两个返回值都设为-1
*/
vector<int> searchRange(vector<int>& nums, int target) {
    if(nums.empty())    return vector<int>{-1,-1};
    int lower=lower_bound(nums,target);
    int upper=upper_bound(nums,target)-1;   //注意
    if(lower==nums.size() || nums[lower]!=target)   //注意
        return vector<int>{-1,-1};
    return vector<int>{lower, upper};
}
//lower_bound
int lower_bound(vector<int>& nums, int target){
    int l=0,r=nums.size(),mid;
    while(l<r){
        mid=(l+r)/2;
        if(nums[mid]>=target) r=mid;
        else l=mid+1;   //注意+1
    }
    return l;
}
//upper_bound
int upper_bound(vector<int>& nums, int target){
    int l=0,r=nums.size(),mid;
    while(l<r){
        mid=(l+r)/2;
        if(nums[mid]<=target) l=mid+1;  //注意+1
        else r=mid;
    }
    return l;
}


//81.搜索旋转排序数组
/*
一个原本增序的数组被首尾相连后按某个位置断开（如[1,2,2,3,4,5]->[2,3,4,5,1,2]，在第一位和第二位断开)，我们称其为旋转数组。给定一个值，
判断这个值是否存在于旋转数组中。
题解：即时数组被旋转过，我们仍然可以利用这个数组的递增性，使用二分查找。对于当前的中点，如果它指向的值小于等于右端，那么说明右区间是排好序的；
反之那么说明左区间是排好序的。如果目标值位于排好序的区间内，我们可以对这个区间继续二分查找；反之我们对另一半进行二分查找。
    注意，因为数组存在重复数字，如果中点和左端的数字相同，我们并不能确定是左区间全部相同，还是右区间完全相同。在这种情况下，我们可以简单的将
左端点右移一位，然后继续进行二分查找。
总结：二分查找 首先mid，mid==target return 1;mid将数组一分为二，肯定有一个有序的，判断target是否在其中，二分查找只针对有序的数组使用。
*/
bool search(vector<int>& nums, int target) {
    //二分查找
    int start=0, end=nums.size()-1,mid;
    while(start <= end){    //注意等号
        mid = (start+end)/2;
        if(nums[mid]==target) return true;

        if(nums[mid]==nums[start]){ //因为数组内可能有重复的数字，无法判断哪边是有序的
            start++;
        }
        else if(nums[mid] <= nums[end]){ //右边是有序的
            if(target > nums[mid] && target <= nums[end]){
                start=mid+1;
            }else{
                end=mid-1;
            }
        }else{  //左边是有序的
            if(target < nums[mid] && target >= nums[start]){
                end=mid-1;
            } else {
                start=mid+1;
            }
        }
    }
    return false;
}