二分法模板

对于任意一个二分法，我们是有如下的形式的，二分法的用途：在一个答案区间内，利用O(\log n)时间复杂度找到答案

int binarySearch(vector& vec, int left, int right, function f){
	while(left < right){
        // 计算 mid
        int mid = left + right >> 1; // (left + right) / 2，右移更快速
        int mid = (right - left >> 1) + left; // (right - left) / 2 + left = (left + right) / 2，防止越界
        
        // 检查 mid，是三种或者两种可能，即 if else-if else或者 if else
        // 三种情况一般这么写
        if(f(mid) > 0){
            left = mid + 1;
        }else if(mid < 0){
            right = mid - 1;
        }else{
            return mid;
        }
        
        // 两者情况一般这么写
        if(f(mid)){
            left = mid + 1;
        }else{
            right = mid;
        }
    }
    return left;  // 有时候会对最终结果进行检测
}

上面就是一个二分法的经典模板了，那么有没有变化呢？

区间

上面是对[\text{left}, \text{right})进行检测，也就是最终结果是\text{result}\in[\text{left}, \text{right})，但是如果我们的结果会\text{result}\in(\text{left}, \text{right}]呢？

其实很简单，由于我们的二分法只能对整数进行操作，所以我们可以选择重新定义我们的区间，比如：\text{result}\in[\text{left}+1, \text{right}+1)即可。

同理，对于下面的区间，我们可以套用这个模板，但是需要更换起始区间即可。

• \text{result}\in[\text{left}, \text{right})\rightarrow\text{init}()\{\text{l}=\text{left},\text{r}=\text{right}\}
• \text{result}\in[\text{left}, \text{right}]\rightarrow\text{init}()\{\text{l}=\text{left},\text{r}=\text{right}+1\}
• \text{result}\in(\text{left}, \text{right}]\rightarrow\text{init}()\{\text{l}=\text{left}+1,\text{r}=\text{right}+1\}
• \text{result}\in(\text{left}, \text{right})\rightarrow\text{init}()\{\text{l}=\text{left+1},\text{r}=\text{right}\}

这样子，就可以不用换模板了。当然，下面也可以给出另一种解决方法，但是更加推荐换区间的解决方法。

...
        int mid = left + right + 1 >> 1; // 向上取整
...
        
        // 两者情况一般这么写
        if(f(mid)){
            left = mid;  // 这是由于mid会更加倾向于right了，所以left不能随意超过mid，因为mid的时候一定是满足要求的，mid+1不一定满足要求
        }else{
            right = mid - 1;  // 
        }
    }
    return left;  // 有时候会对最终结果进行检测
}

条件语句

前面的条件语句是不能直接抄的，需要有所更改

三结果

这种情况往往是需要返回满足的值，找一个结果满足恰好满足题意的答案，且不大不小的那种。下面给出样例

在递增数组中寻找target是否存在并返回下标，如果有多个，任意一个都可以，如果不存在返回 -1：

// 思路分解：
// 		答案区间：[0, n)
//		返回条件，v[mid] == target

int binarySearch(vector<int>& v, int target){  // v是非递减数组
    // 1. 定义检查函数，这里用lambda表达式替代
    // 		返回1，表示当前结果偏小，需要增大
    // 		返回0，表示当前结果刚刚好
    //		返回-1，表示当前结果偏大，需要减小
    auto check = [&](int mid){
        if(v[mid] > target){
            // 现象：当前 mid 值使得结果大于目标值
            // 若要达到题意，需减小 v[mid]
            // 若要减小v[mid]，需减小 mid
            // 减小mid，返回-1
            return -1
        }else if(v[mid] < target){
            // 现象：当前 mid 值使得结果小于目标值
            // 若要达到题意，需增大 v[mid]
            // 若要增大v[mid]，需增大 mid
            // 增大mid，返回1
            return 1;
        }else{
            // v[mid] == target
            // 满足要求，返回0
            return 0;
        }
    };
	int n = v.size();
    int left = 0, right = n;
    while(left < right){
        int mid = left + right >> 1;
		int cur_direction = check(mid);
        if(cur_direction == 1){
            // 需要增大，mid往右边靠近
            // 左边的是不需要了的
            // left就往右移动
            left = mid + 1;
        }else if(cur_direction){
			// 需要减小，mid往左边靠近
            // 右边的是不需要了的
            // right就往左移动
            right = mid - 1;
        }else{
            return mid;
        }
    }

    // 最终结果要么是 left == right，要么是 right == left - 1
	// 但是结果一定是在 left 的，因为向下取整，mid会更可能检测left的值，当然也有可能没检测
	// 由于区间是[left, right)，同样需要判断 left 在不在这个区间
	if(left < n and left >= 0){
		// 由于left的值未必就被检测过，所以还需要判断
        return v[left] == target ? left : -1;
    }
	return -1;
}

二结果

这种情况往往是找到一个最大或者最小满足题意的值，下面给出最大和最小的两个样例

1. 在递增数组中找到一个最大下标，满足要求：该下标对应的值小于target（如果是大于等于target，那么其实就是检查最后一个即可，所以没意义）

2. 在递增数组中找到一个最小下标，满足要求：该下标对应的值大于等于target（如果是小于target，那么其实就是检查第一个即可，所以没意义）

值得注意的是，这里一方面用了大于等于，另一方面用了小于，其实本质都一样的

示例1

int binarySearch(vector<int>& v, int target){
	auto check = [&](int mid){
        // 对应下标，小于target，可以返回true
		if(v[mid] < target) return true;
        // 否则返回false，当然，这个可以直接写成 return v[mid] < target;分开写更加清楚一点
        return false;
    };
    int n = v.size();
    int left = 0, right = n;
    while(left < right){
        int mid = left + right >> 1;
        if(check(mid)){
            // 当前mid还是满足要求，我们可以尝试继续增大它
            // 由于我们检测了当前值 mid，最终退出循环会检测 left 的值，所以可以让 left 大于 mid
            // 如果 left 直接为 mid，可能会陷入死循环，因为在right = left+1的时候，mid会等于left
            left = mid + 1;
        }else{
            // 当前要求已经不满足了，我们就不可以增大了
            // 不能写成 right = mid - 1;
            // 因为我们的mid不会检测right的值，mid永远不会主动等于right
            // 并且退出循环后，不会检测right的值
            right = mid;
        }
    }
    // 检测left的值
    if(left < n and left >= 0){
        if(check(left)){
            return true;
        }
    }
    return false;
}

示例2

int binarySearch(vector<int>& v, int target){
	auto check = [&](int mid){
		return v[mid] >= target;
    };
    int n = v.size();
    int left = 0, right = n;
    while(left < right){
        int mid = left + right >> 1;
        if(check(mid)){
			right = mid;  // 满足要求，还要尽可能小
        }else{
			left = mid + 1; // 不满足要求，得增大了
        }
    }
    // 检测left的值
    if(left < n and left >= 0){
        if(check(left)){
            return true;
        }
    }
    return false;
}