考完了计算机三级，蓝桥杯和数学建模的学习也要恢复常态啦！今天，我们来了解一种相对简单但容易出错的算法——二分查找。这里还有一些小方法让二分查找没有那么容易出错，开始学习吧啦啦啦！
PS： 文章主要参考：b站 一只会code的小金鱼 的视频（真的讲得超级超级详细！！！很适合大一没接触过算法的小白学习，而且up的声音也很好听很好听！！！墙裂推荐！）
基本思路
如上图：
查找的对象是一个已经排列好顺序的数的序列，这里要想像一个不存在的红蓝边界，要找的那个数就是红蓝边界，为了找到那个数，先找头尾l和r（-1，n），再找一个中间值，即m=，如果m属于蓝色，那么头就变成m，如果属于红色，尾就变成m，依次查找直到头+1=尾
l I r
初始：l指向蓝色区域，r指向红色区域
循环：l，r快速向红蓝边界靠近，保持l，r颜色不变
时间复杂度：O（log n）
注意：l初始位置为-1，r的初始位置为N，防止出现如下情况：
5 5 8 9
在上面的数组中查找<=4的数出现的位置，如果l初始=0，就会出现错误
一定要让l初始在蓝，r初始在红！
I 5 5 8 9
l初始位置为-1，r的初始位置为N，则黄色即为边界，程序马上退出循环体
核心就是这段伪代码啦：
注意：Isblue中，blue的判断条件 是blue的条件，如<5(下图例1)
这些查找都可以用c++中 的库函数，但二分题型很多，还是掌握根本比较好
解题步骤
精析一组题
例：
数组： 3 4 4 5 5 5 6 7
分析红蓝条件，找到边界，找到第一个>5的元素的下标
数组： 3 4 4 5 5 5 I 6 7
下标： 1 2 3 4 5 6 7 8
主体：
int l=0,r=9;
while(l+1!=r)
{
int mid (l+r)/2;
if(isblue(q[mid]))
{
l=mid;
}
else r=mid;
if(arr[l]==5)
{
return r;
}
}isblue:
bool isblue(int x)
{
if(x<=5)
return true;
else
return false
}题目变形：
数组： 3 4 4 5 5 5 6 7
分析红蓝条件，找到边界，找到第一个<=5的元素的下标
数组： 3 4 4 5 5 5 I 6 7
下标： 0 1 2 3 4 5 6 7 //注意下标变成1了
int l=-1,r=8;
while(l+1!=r)
{
int mid (l+r)/2;
if(isblue(q[mid]))
{
l=mid;
}
else r=mid;
if(arr[l]==5)
{
return l;
}
}
bool isblue(int x)
{
if(x<=5)
return true;
else
return false
}例题 数的范围
题目：
答案：
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=100010;
int n,q;
int arr[N];
//数组中的数是num,被询问数是x
bool isBlue1(int num,int x)
{
if(num<x) return true;
else return false;
}
//第一个二分查找的是 被询问数第一次出现的位置（下标）
bool isBlue2(int num,int x)
{
if(num<=x) return true;
else return false;
}
//第二个二分查找的是 被询问数最后一次出现的位置（下标）
int binary_search1(int q[],int len,int x)
{
int l=-1,r=len;
while(l+1<r)
{
int mid=(l+r)/2;
if(isBlue1(q[mid],x))
{
l=mid;
}
else r=mid;
}
if(arr[r]==x) return r;
else return -1;
}
int binary_search2(int q[],int len,int x)
{
int l=-1,r=len;
while(l+1<r)
{
int mid=(l+r)/2;
if(isBlue2(q[mid],x))
{
l=mid;
}
else r=mid;
}
if(arr[r]==x) return l;
else return -1;
}
int main()
{
scanf("%d %d",&n,&q);
for(int i=0;i<n;i++)
{
scanf("%d",&q[i]);
}
while(q--)
{
int x;
scanf("%d",&x);
int res1=binary_search1(arr,n,x);//查找数起始下标
//优化：
if(res1==-1)
{
printf("-1 -1\n");
continue;
}
int res2=binary_search2(arr,n,x);//查找数终止下标
}
printf("%d %d\n",res1,res2);
return 0;
} 
