前言

        在信奥中，二分算法是一种非常重要的方法。利用它，我们在某些场合中寻找数时就不必要遍历数组，大大提高了效率。今天我们来学习二分算法的基本方法。

程序设计思路

        有这样一个问题：给你一个数组，数组里面的数已经按数值大小倒序排列，请从中找到某个数，要求不得遍历数组。

        这里需要注意，数组里的数已经降序排列，这一点对我们要进行的查找是有帮助的。我们可以利用数之间的大小关系，进行查找。比如说，可以先找到数组中间的那个数，与基准数（要找的数）进行比较。如果基准数大于这个数，那么我们就可以确定基准数在这个数的左侧，反之则在这个数的右侧。这样一直循环，直到找到基准数。

        这就是二分查找的精髓。

代码实现

        直接看题：

        这是二分算法的模板题，思路已经有了，直接上代码——

#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，再见！

本文链接：https://blog.faryou.eu.org/post/100.html 转载需经作者授权！