前言
回顾之前初学循环时写过的猜数小游戏，若范围是0~100，大多数人的猜法都是先猜50，若大了，则猜25；若小了，则猜75......这种搜索方法，就是二分搜索。
一、二分搜索原理
二分搜索的原理很简单，但非常实用。二分搜索时，每次都把有序数组分成两份，判断中点位置的值和要搜索的值的大小关系，然后进行下一步搜索。
二、例题
1.有序数组搜索n
#include<bits/stdc++.h>
using namespace std;
//二分搜索
int search(int num,vector<int>n)
{
int l=0;
int r=n.size()-1;
int m=0;
// int cnt=0;
while(l<=r)
{
m=(l+r)/2;
// cout<<"m : "<<m<<endl;
if(n[m]==num)
{
// cout<<cnt+1<<endl;
return m;
}
else if(n[m]>num)
{
r=m-1;
}
else
{
l=m+1;
}
// cnt++;
// cout<<cnt<<"..."<<endl;
}
return 0;
}
int main()
{
vector<int>n;
for(int i=1;i<=100;i++)
{
n.push_back(i);
}
int num;
cin>>num;
int result=search(num,n);
if(result)
{
cout<<"Found In "<<result;
}
else
{
cout<<"Not Found";
}
return 0;
}因为数组有序，所以可以对其使用二分搜索。
首先设置变量l表示起始位置，r表示结束位置，m表示中点位置。
然后，只要当l<=r，即可以继续二分，就判断中点值和搜索值，若相等则返回m；若大于搜索值则让r=m-1；若小于则让l=m+1，然后继续二分，知道搜索到或不存在为止。
2.有序数组返回>=num的最左侧位置
#include<bits/stdc++.h>
using namespace std;
//二分搜索大于等于num的最左侧位置
int search(int num,vector<int>n)
{
int l=0;
int r=n.size()-1;
int m=0;
int ans=-1;
// int cnt=0;
while(l<=r)
{
//m=(l+r)/2;
m=l+(r-l)/2;//防溢出
// cout<<"m:"<<m<<endl;
if(n[m]>=num)
{
ans=m;
r=m-1;
}
else
{
l=m+1;
}
// cnt++;
// cout<<cnt<<"..."<<endl;
}
return ans;
}
int main()
{
vector<int>n;
for(int i=2;i<=100;i+=2)
{
n.push_back(i);
}
int num;
cin>>num;
int result=search(num,n);
if(result!=-1)
{
cout<<result;
}
else
{
cout<<"Not Exist";
}
return 0;
}首先，除了l,m,r，还需要设置ans变量来记录位置。这里，l+(r-l)/2同样可以取l和r的中点，其优点是，在l和r特别大时，可以防止数据溢出。
若中点值大于等于num，则更新ans，使其等于此时的中点值；若小于则不更新ans。直到不可继续二分，则循环结束，返回ans。
同理，有序数组返回<=n的最右侧位置类似。
3.无序数组找极大值点
#include<bits/stdc++.h>
using namespace std;
//二分搜索无序数组中的极大值
int search(vector<int>n)
{
//先判断端点
int len=n.size();
if(n[0]>n[1])
{
return 0;
}
if(n[len-1]>n[len-2])
{
return len-1;
}
int l=0;
int r=len-2;
int m=0;
int ans=-1;
while(l<=r)
{
m=(l+r)/2;
if(n[m-1]>n[m])
{
r=m-1;
}
else if(n[m+1]>n[m])
{
l=m+1;
}
else
{
ans=m;
break;
}
}
return ans;
}
int main()
{
vector<int>n;
int a;
for(int i=0;i<10;i++)
{
cin>>a;
n.push_back(a);
}
int result=search(n);
if(result!=-1)
{
cout<<result;
}
else
{
cout<<"Not Found";
}
return 0;
}与之前不同，这里是无序数组，但我们依然可以使用二分搜索。
根据导数的零点存在定理（没想到吧这里也有高数！）可知，在闭区间[a,b]上，若f(a)*f(b)<0，则存在f(x)=0。由此可知，若可以判断两端点的导数之积小于零，即函数趋近两端点的单调性相反，则中间必存在导数为0的点。进一步可知，若导数趋近左端点时大于零，趋近右端点时小于零，则中间必存在极大值点。
所以，我们先判断左右端点是否为极大值。若均不是，根据以上原理则说明中间必存在极大值点。此时，我们就可以使用二分搜索。若m-1的值大于m，则说明中点的左导数小于零，则说明左侧必有极大值；若m+1的值大于m，说明中点的右导数大于零，则说明右侧必有极大值；若均不满足，则此时m点即为极大值点。
总结
即使第三题为无序数组，依然可以使用二分搜索。由此可得，二分搜索的条件可以推广到，只要通过判断某点值和目标值的大小，可以确定该点一侧必存在或一侧必不存在目标值，就可以使用二分搜索。