“二分查找”

二分查找模板

#include<iostearm>
using namespace std;
int main()
{
    vector<int> nums(n);
    int target;
    int left = 0 , right = n -1;
    //关于满足条件的左右区间变换问题 // 两端区间为左闭右闭
    // 0 1 2 3 4 5 
    // 当 left = 0 , right = 5 ;
    while(left < right)
    {
        //mid = (0 + 5) / 2 = 2 , mid为  {0,1,2} , {3,4,5};
        int mid = (left + mid)/2;//
        if (nums[mid] == target)
            return mid;
       	if (nums[mid] > target)
            right = mid;//mid就是左半区的终止位置
       	else
            left = mid + 1;//右半边,需要+1，才能取到右半区的起始位置
    }
    while(left < right)
    {
        //mid = (0 + 5 + 1) / 2 = 3 , mid为  {0,1,2} , {3,4,5};
        int mid = (left + mid + 1)/2;//
        if (nums[mid] == target)
            return mid;
       	if (nums[mid] > target)
            right = mid - 1;// 如果缩小为左半区，right (2) 需要 mid - 1 (3-1)
       	else
            left = mid; // 如果缩小为右半区，left (3) 就为mid
    }
}