前言
在信奥中，二分算法是一种非常重要的方法。利用它，我们在某些场合中寻找数时就不必要遍历数组，大大提高了效率。今天我们来学习二分算法的基本方法。
程序设计思路
有这样一个问题：给你一个数组，数组里面的数已经按数值大小倒序排列，请从中找到某个数，要求不得遍历数组。
这里需要注意，数组里的数已经降序排列，这一点对我们要进行的查找是有帮助的。我们可以利用数之间的大小关系，进行查找。比如说，可以先找到数组中间的那个数，与基准数（要找的数）进行比较。如果基准数大于这个数，那么我们就可以确定基准数在这个数的左侧，反之则在这个数的右侧。这样一直循环，直到找到基准数。
这就是二分查找的精髓。
代码实现
直接看题：
这是二分算法的模板题，思路已经有了，直接上代码——
#include <bits/stdc++.h>
int a[1000005],n,m,aq;//a存输入的数据，n、m同题意，aq临时存要查找的数
int search(int iq){
int left=1,right=n,mid=(1+n)/2;//确定左指针、右指针、中央
while(left<right){//当左右指针相遇时，循环结束
mid=(left+right)/2;
if(a[mid]>=iq) right=mid;
else left=mid+1;
}//不断更新左、右、中指针
if(a[left]==iq) return left;
else return -1;
}
int main(){//main里全是输入和输出，不讲了
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=m;i++){
scanf("%d",&aq);
printf("%d ",search(aq));
}
return 0;
}可以看到，这里使用了左右两个指针解决问题。程序并不难写，关键在思路。
总结
二分算法是一种能够大大提升查找效率的方法。之后我还会为大家带来由二分算法衍生出的二分答案和三分算法。我是faryou，再见！