一、二分查找
关键：确定待查找的元素出现在什么区间内，循环不变量:目标值一定在当前搜索范围内。
模板一:在左闭右闭区间内查找目标元素
由于待查找元素在左闭右闭区间，因此要想在已有数组内查找该元素，就要让初始左右指针分别为0，size-1(刚好覆盖整个数组)。
判断循环结束条件，即什么时候左右区间内不存在元素，由于是全闭区间，因此当两个指针相等时，依然存在元素，所以只有当左指针在右指针右侧时，出现不合法区间，这时区间内不存在元素，即l>r退出，循环条件为l<=r。
令mid=(l+r)/2(此为下取整，也可上取整)(因为每次迭代如果没找到目标元素必然会压缩区间)，为防止溢出可令mid=l+(r-l)/2。每次迭代需要更新区间，当mid位置不为目标元素时，可以想象成原数组被mid分割成两个部分，根据左闭右闭性质(两个区间不需要包含mid)。因此当mid元素小于目标元素时，说明目标元素在右区间，此时令l=mid+1，当mid元素大于目标元素时，说明目标元素在左区间，此时令r=mid-1，当mid元素等于目标元素时，则找到，下标为mid。
代码:
class Solution {
public:
int search(vector<int>& nums, int target) {
int l=0,r=nums.size()-1;
while(l<=r)
{
int mid=l+(r-l)/2;
if(nums[mid]<target) l=mid+1;
else if(nums[mid]>target) r=mid-1;
else return mid;
}
return -1;
}
};模板二:在左闭右开区间内查找目标元素
由于待查找元素在左闭右开区间，要想在整个数组内查找该元素，就要让初始左右指针分别为0,size,即右指针要在待查找数组最右元素的右边。
判断循环结束条件，即什么时候左右区间内不存在元素，由于当左右指针相等时，该区间内不包含任何元素，因此l=r时循环退出，即循环条件为l<r；
令mid=(l+r)/2，为防止溢出可令mid=l+(r-l)/2，注意这里不能上取整，因为会出现死循环(后面解释)。每次迭代需要更新区间，当mid元素不为目标元素时，则在左右两个区间寻找目标元素，根据左闭右开原则，更新时右指针要在新待查找数组的最右元素的右侧，左指针和上面的模板一样，因此当mid元素小于目标元素时，说明目标元素在右区间，此时令l=mid+1，当mid元素大于目标元素时，说明目标元素在左区间，此时待查找数组的最右元素下标为mid-1，所以令r=mid(因此当采用上取整时，若区间为[4，5)，则mid=r=5，如果遇到这种情况，迭代后区间仍未改变，陷入死循环)，当mid元素等于目标元素时，则找到，下标为mid。
代码:
class Solution {
public:
int search(vector<int>& nums, int target) {
int l=0,r=nums.size();
while(l<r)
{
int mid=l+(r-l)/2;
if(nums[mid]<target) l=mid+1;
else if(nums[mid]>target) r=mid;
else return mid;
}
return -1;
}
};模板三:在左开右闭区间内查找目标元素
与模板二类似，区别在于三个地方，首先是初值初值l=-1，r=num.size()-1；其次是mid指针需要上取整，避免死循环，比如(3,4]，mid=l，会遇到迭代后区间不变的情况；最后是迭代后的更新指针，当mid元素小于目标元素时，说明目标元素在右区间，左指针需要在最左元素的左侧，此时令l=mid，当mid元素大于目标元素时，说明目标元素在左区间，此时令r=mid-1。
代码:
class Solution {
public:
int search(vector<int>& nums, int target) {
int l=-1,r=nums.size()-1;
while(l<r)
{
int mid=l+(r-l+1)/2;
if(nums[mid]<target) l=mid;
else if(nums[mid]>target) r=mid-1;
else return mid;
}
return -1;
}
};模板四:在左开右开区间内查找目标元素
由于待查找元素在左开右开区间，要想在整个数组内查找该元素，就要让初始左右指针分别为-1,size,即左指针要在待查找数组最左元素的左边，右指针要在待查找数组最右元素的右边。
判断循环结束条件，即什么时候左右区间内不存在元素，由于当l+1=r或者l=r-1时，该区间内不包含任何元素，因此l+1=r或者l=r-1时循环退出，即循环条件为l+1<r。
令mid=(l+r)/2(此为下取整，也可上取整)(因为循环条件为l+1<r，因此不会出现左右指针相邻的情况，所以每次迭代不会出现区间不变的情况)，为防止溢出可令mid=l+(r-l)/2。每次迭代需要更新区间，当mid元素不为目标元素时，则在左右两个区间寻找目标元素，根据左开右开性质，左指针要在待查找数组最左元素的左边，右指针要在待查找数组最右元素的右边。因此当mid元素小于目标元素时，说明目标元素在右区间，此时令l=mid，当mid元素大于目标元素时，说明目标元素在左区间，此时令r=mid，当mid元素等于目标元素时，则找到，下标为mid。
代码:
class Solution {
public:
int search(vector<int>& nums, int target) {
int l=-1,r=nums.size();
while(l+1<r)
{
int mid=l+(r-l)/2;
if(nums[mid]<target) l=mid;
else if(nums[mid]>target) r=mid;
else return mid;
}
return -1;
}
};例题:35. 搜索插入位置 - 力扣（LeetCode）
采用模板1，二分查找目标元素位置，若查到，则返回mid，若不存在，则根据迭代时更新l=mid+1,r=mid-1，可知当循环结束时，如果是l=mid+1导致的，则说明当前l左侧的都比目标元素小，即l当前指向的元素可能大于目标元素，如果是r=mid-1导致的，则说明r右侧的都比目标元素大，即r当前指向的元素可能小于目标元素，由题意，要返回插入位置，因此返回l。
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int l=0,r=nums.size()-1;
while(l<=r)
{
int mid=l+(r-l)/2;
if(nums[mid]>target) r=mid-1;
else if(nums[mid]<target) l=mid+1;
else return mid;
}
return l;
}
};二、二分推广
二分答案:
二分答案是一种通过二分法 在方案范围内搜索最优解 的算法思想。它通常用于解决 最优化问题 或 满足某种条件的最小/最大值问题。
关键:不断缩小最优方案出现的范围。
类似于二分查找中在整个有序数组中寻找目标元素，二分答案是在所有方案(具有广义单调性，即左区间满足某一性质，而右区间不满足该性质)中寻找满足要求的最优方案，如果要求比较复杂，需要编写check函数，使得当前方案符合要求时返回true。
因此，首先要找到所有方案的范围，确定边界(l,r指针)，与二分查找不同，由于是查找最优方案，而不是满足要求就行，因此在mid处的方案满足要求时(check(mid)==true)，仍要更新区间，根据问题不同选择不同的更新方式。此外，由于迭代的最终目标是使得方案归一，因此循环结束条件为l==r，因此为了确保最终返回的指针在所有方案内，所以l,r指针要初始化为所有方案中的最小和最大，而不是类似l=-1或r=num.size()。
注意，最终要检查归一的方案是否满足要求，如果不满足，则说明所有方案都不成立。
1.寻找最靠近左边界的方案:(最小的满足条件的值)，类似模板二，初值不同
因此当mid处的方案满足要求时，要将区间压缩为左侧，即更新r指针，r=mid，因此为避免死循环，使用下取整。
伪代码:
int l=最小方案，r=最大方案;
while(l<r)
{
int mid=l+(r-l)/2;
if(check(mid)) r=mid;//check()为判断当前方案是否满足条件的函数
else l=mid+1;
}
if(!check(l)) return false;
else return l;//由于最终l和r相等，因此都可以，一般左边界问题常用l,右边界问题常用r。2.寻找最靠近右边界的方案:(最大的满足条件的值)，类似模板三，初值不同
因此当mid处的方案满足要求时，要将区间压缩为右侧，即更新l指针，l=mid，因此为避免死循环，使用上取整。
伪代码:
int l=最小方案，r=最大方案;
while(l<r)
{
int mid=l+(r-l+1)/2;
if(check(mid)) l=mid;//check()为判断当前方案是否满足条件的函数
else r=mid-1;
}
if(!check(l)) return false;
else return r;//由于最终l和r相等，因此都可以，一般左边界问题常用l,右边界问题常用r。例题:34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）
第一个位置即左边界问题，最后一个位置即右边界问题
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int l=0,r=nums.size()-1;
vector<int> result(2, -1);
if (nums.empty()) return result;
while(l<r)
{
int mid = l+(r-l)/2;
if(nums[mid]>=target) r=mid;
else l=mid+1;
}
if(nums[l]!=target) return result;
else
{
result[0]=l;
int l=0,r=nums.size()-1;
while(l<r)
{
int mid=l+(r-l+1)/2;
if(nums[mid]<=target) l=mid;
else r=mid-1;
}
result[1]=r;
}
return result;
}
};例题:35. 搜索插入位置 - 力扣（LeetCode）
采用二分答案的思路，二分插入位置。因此合法的边界为l=0,r=num.size()。使用左边界模板，因为要求为第一个大于等于target的位置。
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int l=0,r=nums.size();
while(l<r)
{
int mid=l+(r-l)/2;
if(nums[mid]>=target) r=mid;
else l=mid+1;
}
return l;
}
};三分查找:
关键:通过在[l,r]设置两个指针midl,midr，不断迭代，将极值点控制在足够小的范围内。
三分查找是一种用于在单峰函数中寻找极值的算法。它通过将搜索区间分为三部分，逐步缩小范围，最终找到极值点。需要在区间内设置两个指针(二分只有一个mid指针)midl,midr(通过将区间均分成3份来得到这两个指针)，通过迭代将l和r控制在足够小的范围内，最终确定极值点。针对极大值和极小值，三分查找有所不同。
查找极大值:
思路:分为三种情况:
情况一:如果f(midl)<f(midr)，可能的情形如下所示
因此极值会出现在[midl,r]之间，将l更新为midl。
情形二:如果f(midl)>f(midr)，可能的情形如下所示
因此极值会出现在[l,midr]之间，将r更新为midr。
情形三(可以合并到上面两个情形中):如果f(midl)==f(midr)，可能的情形如下所示
因此极值点会出现在[midl,midr]之间，将l更新为midl，r更新为midr。
代码:
double ternary_search_max(double left, double right, double epsilon = 1e-6) {
while (abs(right - left) >= epsilon) {
double midl = left + (right - left) / 3;
double midr = right - (right - left) / 3;
if (f(midl) < f(midr)) {//f()为某一个函数，如f(x)=−x^2+6x−5
left = mid1; // 极大值在 [midl, right]
} else {
right = mid2; // 极大值在 [left, midr]
}
}
return (left + right) / 2;
}
查找极小值:
思路:分为三种情况:
情况一:如果f(midl)>f(midr)，可能的情形如下所示
因此极值会出现在[midl,r]之间，将l更新为midl。
情况二:如果f(midl)<f(midr)，可能的情形如下所示
因此极值会出现在[l,midr]之间，将r更新为midr。
情况三:同极大值。
代码:
double ternary_search_min(double left, double right, double epsilon = 1e-6) {
while (abs(right - left) >= epsilon) {
double midl = left + (right - left) / 3;
double midr = right - (right - left) / 3;
if (f(midl) > f(midr)) {
left = midl; // 极小值在 [midl, right]
} else {
right = midr; // 极小值在 [left, midr]
}
}
return (left + right) / 2;
}以上是以浮点型为例，若为整型会所有不同。
三分法通常采用全闭区间，当l==r时，说明该点就是极值点，可以退出循环，因此循环条件为l<r。下仅以寻找极大值为例，为了避免取整时会出现midl=midr，将midr设置为midl+1。
情况1:如果nums[midl]<nums[midr]，可能的情形如下所示
因此极大值会出现在[midl+1,r]之间(为什么不是midl，而是midl+1，因为midl已经比midr小了，所以一定不是极大值)，将l更新为midl+1。
情况2:如果nums[midl]>=nums[midr]，可能的情形如下所示
例题:162. 寻找峰值 - 力扣（LeetCode）
由于找到任意个极值都可以，因此可以看作存在一个极值，按照整数三分查找即可。
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int l=0,r=nums.size()-1;
while(l<r)
{
int midl=l+(r-l)/2;
int midr=midl+1;
if(nums[midl]<nums[midr]) l=midl+1;
else r=midr-1;
}
return l;
}
};