最近，刷题遇到了二分法的题目，感觉绝大多数题目都是一个同样的套路：

做100道题，不如静下心来总结几道题，将使用二分法的场景，使用二分法的步骤捋一捋，这样就是真正掌握了核心技术，而不是简单地背几个模板，有的可以应付过去，稍微变形一下，就无法动弹；

1 首先是找元素，二分法可以使用对数级别的时间复杂度


例如： {1,2,3,4,4,5,6} ， 想要找到里面第一个4的位置；
思路就是：每次取中点的元素，将其与target进行比较，如果小于4，说明4在右半部分，因此需要更新left；否则就是在左半部分，更新right； 
int BinarySearchFisrt(std::vector<int> &nums, int target)
{
   
    if(!nums.size())
        return -1;
    int left = 0, right = nums.size() - 1;
    while (left < right)
    {
   
        int mid=left+(right-left)/2;
        if(nums[mid]<target)
            left=mid+1;
        else if(nums[mid]>target)
            right=mid-1;  
        else 
            right=mid;
    }
    return (left<nums.size() && nums[left]==target )? left:-1;
}


想要找到最后一个4

int BinarySearchLast(std::vector<int> &nums, int target)
{
   
    if(!nums.size())
        return -1;
    int left = 0, right = nums.size() - 1;
    while (left < right)
    {
   
        int mid=left+(right-left+1)/2;
        if(nums[mid]<target)
            left=mid+1;
        else if(nums[mid]>target)
            right=mid-1;  
        else 
            left=mid;
    }
    return (left<nums.size() && nums[left]==target )? left:-1;
}


总结：
其实，就是将三种情况拎出来进行讨论，然后需要注意的是，当我们寻找右边界的时候，注意，mid需要向上取整，不然会出现死循环的情况

#include <iostream>
#include <vector>

int BinarySearchFisrt(std::vector<int> &nums, int target)
{
   
    if(!nums.size())
        return -1;
    int left = 0, right = nums.size() - 1;
    while (left < right)
    {
   
        int mid=left+(right-left)/2;
        if(nums[mid]<target)
            left=mid+1;
        else if(nums[mid]>target)
            right=mid-1;  
        else 
            right=mid;
    }
    return (left<nums.size() && nums[left]==target )? left:-1;
}

int BinarySearchLast(std::vector<int> &nums, int target)
{
   
    if(!nums.size())
        return -1;
    int left = 0, right = nums.size() - 1;
    while (left < right)
    {
   
        int mid=left+(right-left+1)/2;
        if(nums[mid]<target)
            left=mid+1;
        else if(nums[mid]>target)
            right=mid-1;  
        else 
            left=mid;
    }
    return (left<nums.size() && nums[left]==target )? left:-1;
}

int main()
{
   
    std::cout << "test!" << std::endl;
    std::vector<int> A={
   5,7,7,8,8,10,11};
    int first=BinarySearchFisrt(A,8);
    int last=BinarySearchLast(A,8);
    return 0;
}