二分法模板

假设vec从小到大

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

把这部分代码，分成若干部分来分析

第一部分

while(left < right){
    ...
}

return vec[left] == target ? left : -1;

有些可以写作left <= right，本身这两种也没有什么区别，只在最后的return取值有区别，也就是循环终止条件不一样

第二部分

int mid = (left + right) / 2;

// 以下写法都是等价的
int mid = (left + right) >> 1;
int mid = left + (right -  left) / 2;
int mid = left + ((right - left) >> 1);

// 后两种不会超过int类型最大值，假设你的数组长度比较大，那么就得用后面两种，python除外

第三部分

if(vec[mid] < target){
    // how to do
}else if(vec[mid] == target){
    // how to do
}else {
    // how to do
}

这一部分就需要根据自己实际的需求来，下面说的指针均表示mid指针

• 第一行：如果指针指向的 值 小于 目标 ；或者说指针需要向右移动的条件
• 第二行：如果指针指向的 值 等于 目标；或者说指针已经找到目标了
• 第三行：如果指针指向的 值 大于 目标；或者说指针需要向左移动的条件