二分查找题型

在所给的数组中找到那个目标数字

区间定义：[l, r) 左闭右开

 int binary_search(vector<int>& nums,int targe)
{
        int l=0;
        r=nums.size();
        while(l<r)
        {
            mid=l+(r-l)/2;
            m=nums[mid];
            if(m==targe)
                  return targe;
            if else(m> targe)
                    r=mid;         //新的范围  [l,mid)
            else
                l=mid+1;             //新的范围  [mid+1,r)
             
        }
        
        return l;   //或者返回找不到
}

另一种题型：找到目标数字的开始的索引和结束索引，所以就是C++的lower_bound和upper_bound。

这两个函数只有一点不同，就是nums[mid]与target的判断，
lower_bound找到是大于等于目标的元素，所以只有nums[mid] < target时才移动左指针；
而upper_bound是大于目标的元素，所以当nums[mid] <= target就向右移动左指针了。

lower_bound返回的是开始的第一个满足条件的位置，
而upper_bound返回的是第一个不满足条件的位置。所以，当两个相等的时候代表没有找到，
如果找到了的话，需要返回的是[left, right - 1].

用法：

fun()
{
    vector<int> v {1,3,4,5,6,7}；
    auto l=lower_bound(v.begin(),v.end(),3);   //这个函数返回的是第一个大于等于3 的数,所以返回3
    auto r= upper_bound(v.begin(),v.end(),3);//这个函数返回的是第一个大于3 的数,所以返回4
    return {l,r-1}
}
//若是用自己写的函数的话，每个返回值是其下标,用c++的STL的返回值是迭代器

lower_bound(): 找到一个元素, 像 nums[i] >= targe

int lower_bound(vector<int>& nums,int targe)
{
    const int N=nums.size();
            //范围[l,r)
    int l=0;r=N;
            
     while(l<r)
    {
      int mid=l+(r-l)/2;
      int t=nums[mid];
                
    //比如 {1,2,3,4,5}，这是t=nums[2]=3, 若3<targe,我们要的是大于等于目标的数，所以3是不符合的，
      //所以下标一定要往右走一位，可以取到mid+1;
     if(t<targe)      //对比upper_bound()函数，就只有这个if里面的条件不一样
        l=mid+1;         //范围 [mid+1,r)
     else
        r=mid;
    }
            
    return l;
}

upper_bound(): 找到一个元素, 像 nums[i] > targe

int upper_bound(vector<int>& nums,int targe)
{
      const int N=nums.size();
            //[l,r)
     int l=0;r=N;
            
      while(l<r)
      {
         int mid=l+(r-l)/2;
         int t=nums[mid];
         if(t<=targe)
              l=mid+1;         //范围 [mid+1,r)
         else
            r=mid;
       }
            
       return l;  
}