算法精讲【整数二分】（实战教学）
---------------模板讲解---------------媒介：
温馨提示：
[*]本片博客博主主要使用口语化的叙述，缘故起因是：下面的内容大部门是博主的做题的心得领会（声明：“博主不是什么算法大佬，仅仅是一位 靠咖啡续命、靠玄学debug的算法咸鱼，分享这篇博客是为了记录自己的学习心得，如果能帮到同样挣扎的你，那就值回咖啡钱了！"）
[*]这篇博客也是博主想到哪就写到哪完成的，以是会有写的不当的地方，还请大佬指正
[*]博客中有一些二分的编程题练习并挂有链接，盼望大家在熟悉了模板之后进行练习加以巩固
[*]每道编程题博主都有提供博主使用模板AC的代码，供大家参考（博主的代码中有大量的解释，记录了博主思索过程）
[*]写这篇博客主要是为了:
[*]教算法小白一个常用的算法：二分查找
[*]资助算法初学者克服对二分的恐惊
在这里博主为正在学算法的你打打气：就算AC率感人，我们也要倔强地WA下去！
学二分查找的痛点：二分查找的思想虽然简朴，但是却极其容易写出死循环，那有有没有什么方法可以使我们又快又好的写出正确的二分查找呢？
深思：出现这种环境的根本缘故起因是二分虽然简朴，但是二分的类型多，且不同种类型的二分的区别并不明显，这就使得我们常常容易搞混，面临具体的问题时一时不知道到底该怎么二分
这里博主将会根据自己的理解重新梳理所有的二分的环境，并尽量的简化模板，方便大家影象。
在博主看来二分从形式上有以下四类：
https://i-blog.csdnimg.cn/direct/77f640f4979f401e9ed0deb10a208efe.png#pic_center
虽然有四种环境，着实我们可以使用一个模板来解决这四种环境
不说废话了，直接给大家上模板
温馨提示：
[*]C++代码的部门是直接可以照抄的部门
[*]伪代码的部门是需要我们根据具体的题意进行随机应变的部门
（下面有讲解应该怎么进行随机应变）
//注意：在给binary_search函数传参时，区间端点(l,r)是开区间
//例如：你想对区间进行二分查找，你应该传入的参数应该是：(l=0,r=10)
int binary_search(int l, int r, int 基准值)
{
while (l + 1 < r)
{
int mid = (l + r) >> 1;
if (待二分数组 </<= 基准值)l = mid;
elser = mid;
}
if (待二分数组 == 基准值) return l/r; //返回的l/r就是目标值的下标
else return -1;
}
应用上面的模板进行二分查找中，只有两个地方需要我们具体环境具体分析：
随机应变1：binary_search函数中l和r该谁进行更新的if判断该怎么写：
[*]if (待二分数组 写<还是<= 基准值)
随机应变2：binary_search函数中函数竣事时该返回什么的if判断该怎么写：
[*]if (q[写l还是r] == 基准值) return 返回l还是r;
疑问：怎样熟练随机应变1？
第一步：要清楚分界线的位置在哪里？
第二步：是写<还是<=，就是根据分界线mid左侧的值和基准值之间的关系决定的
[*]基准值：简朴一点说就是上面的图片中的5
写<或<=总共有2环境：
[*]写<：对应环境1和环境2
[*]写<=：对应环境3和环境4
以是：也就是说只要你可以知道这道题属于二分的哪种环境，随机应变1着实也可以照抄。
疑问：怎样熟练随机应变2？
写l/r和返回l/r组合在一起总共有4种环境：
[*]写r返回l：对应环境1
[*]写r返回r：对应环境2
[*]写l返回l：对应环境3
[*]写l返回r：对应环境4
以是：也就是说只要你可以知道这道题属于哪种环境，随机应变2着实也可以照抄。
说的有点抽象，我们直接看图片演示 + 代码示例：
环境1：找到末了一个<3的元素的位置
https://i-blog.csdnimg.cn/direct/a4005211dfb447a0ac1042f61e402712.png#pic_center
int binary_search(int l, int r, int target)
{
while (l + 1 < r)
{
int mid = (l + r) >> 1;
if (q < 3)l = mid; //随机应变1：写<
elser = mid;
}
if (q == 3) return l;// 随机应变2：写r ，返回l
else return -1;
}
环境2：找到第一个>=3的元素的位置
https://i-blog.csdnimg.cn/direct/0a3e51c186a448f8a6f5cd7fe5ad90ad.png#pic_center
int binary_search(int l, int r, int target)
{
while (l + 1 < r)
{
int mid = (l + r) >> 1;
if (q < 3)l = mid; //随机应变1：写<
elser = mid;
}
if (q == 3) return r;// 随机应变2：写r ，返回r
else return -1;
}
环境3：找到末了一个<=3的元素的位置
https://i-blog.csdnimg.cn/direct/08d561f7190440bfa6ff352d59a8b049.png#pic_center
int binary_search(int l, int r, int target)
{
while (l + 1 < r)
{
int mid = (l + r) >> 1;
if (q <= 3)l = mid; //随机应变1：写<=
elser = mid;
}
if (q == 3) return l;// 随机应变2：写l ，返回l
else return -1;
}
环境4：找到第一个>3的元素的位置
https://i-blog.csdnimg.cn/direct/242fa05eec124f3a857f67ed44dd59ac.png#pic_center
int binary_search(int l, int r, int target)
{
while (l + 1 < r)
{
int mid = (l + r) >> 1;
if (q <= 3)l = mid; //随机应变1：写<=
elser = mid;
}
if (q == 3) return r;// 随机应变2：写l ，返回r
else return -1;
}
---------------经典例题---------------
入门经典例题：789.数的范围
开始挑战： 789.数的范围
https://i-blog.csdnimg.cn/direct/548bcf8b234c45aebef46a4f8531fdbe.png#pic_center
如果你已经把握了上面我讲的内容的话，那么我们不丢脸出这道问题所属的二分类型：
[*]所求元素的起始位置 —> 第2种环境
[*]所求元素的终止位置 —> 第3种环境
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 100010;
int n, q;
int arr;
//第一个二分查找找的是：被询问数的第一次出现的位置(下标)
int binary_search1(int arr[], int len, int x) {
int l = -1, r = len;
while(l + 1 < r)
{
int mid = (l + r) / 2;
if(arr<x)l = mid;
elser = mid;
}
if(arr == x) return r;
else return -1;//找不到就返回-1
}
//第二个二分查找找的是：被询问数的最后一次出现的位置(下标)
int binary_search2(int arr[], int len, int x) {
int l = -1, r = len;
while(l + 1 < r)
{
int mid = (l + r) / 2;
if(arr<= x)l = mid;
elser = mid;
}
if(arr == x) return l;
else return -1;//找不到就返回-1
}
int main()
{
scanf("%d %d", &n, &q);
for(int i = 0; i < n; i++)scanf("%d", &arr);
while(q --)
{
int x;
scanf("%d", &x);
int res1 = binary_search1(arr, n, x);
int res2 = binary_search2(arr, n, x);
printf("%d %d\n", res1, res2);
}
return 0;
}
总结：
虽然我们的方法并不高明，甚至在别人看来是愚蠢的写法，为了写这道题还要两个二分查找函数。
但是我们的方法胜在模板固定，仅需稍作修改每种二分环境便都能使用，并且修改的判断也很简朴。
根本不需要动脑分析什么界限环境，更不会出现死循环的环境，彻底解放
页:
[1]