红绿二分查找

《英雄算法零基础》之 二分查找

https://articles.zsxq.com/id_ib4xgs0cogic.html

在写模版之前我们先搞清楚二分查找是怎样运行的，我们把一个数组分成红绿两种颜色，可以理解为绿色就是符合情况的，红色就是不符合情况的（类似红绿灯，红灯停绿灯行）

isGreen函数

条件判定

判断一个元素是绿色还是红色，我们可以单独用一个函数来实现，根据题意，当值为1时代表绿色，值为0时代表红色，实现如下:

class Solution {// 红红红红红红 绿绿绿绿绿绿int isGreen(int val, int x){if (val == x)return 1;elsereturn 0;}

二分枚举模板

int binarySearch(int left, int right, int x) // 1
{while (left + 1 < right)                 // 2{int mid = left + (right - left) / 2; // 3if (isGreen(mid, x))                 // 4right = mid;                     // 5elseleft = mid;                      // 6}return right;						     // 7}
};  

1. left代表红色游标，right代表绿色游标;
2. 当区间长度大于2的时候，二分缩小区间，这一步被称为区间收敛;
3. mid 为计算出来的区间[left, right]的中点;
4. 判断区间中点对应的元素是 绿色 还是 红色;
5. 如果中点元素是绿色，则从中点到right的值都为 绿色，用中点替换绿色游标;
6. 如果 中点元素 是 红色，则从left到中点的值都为红色，用中点替换红色游标;
7. 这个地方是模板需要变通的地方，如果需要返回红色边界，那么应该返回left;反之，如果需要返回绿色边界则应该返回right。这个模板中是返回后者