C/C++教程

acm算法之二分查找

本文主要是介绍acm算法之二分查找,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
//二分查找,用于快速查找出有序数列中,某元素的下表
#include<iostream>
#include<algorithm>
using namespace std;
int find(int a[],int k)
{
	int mid,right=9,left=0;
	while(right>=left)//为什么 while 循环的条件中是 <=,而不是 < ?   主要是终止条件不同 
	{                     //right 的赋值是 nums.length-1;while(left <= right) 的终止条件是 left == right + 1,写成区间的形式就是 [right + 1, right],
	                      //或者带个具体的数字进去 [3, 2],可见这时候搜索区间为空,因为没有数字既大于等于 33 又小于等于 22 的吧。
	                      //所以这时候 while 循环终止是正确的,直接返回 -1 即可。
                          //while(left < right) 的终止条件是 left == right,写成区间的形式就是 [left, right],
                          //或者带个具体的数字进去 [2, 2],这时候搜索区间非空,还有一个数 22,但此时 while 循环终止了。
                          //也就是说这区间 [2, 2] 被漏掉了,索引 22 没有被搜索,如果这时候直接返回 -1 就是错误的
		mid=(right+left)/2;
		if(a[mid]==k)
		return mid;
		else if(a[mid]>k)
		right=mid-1;
		else if(a[mid]<k)
		left=mid+1;
	}
	return -1;
}
int main()
{
	int a[10];
	for(int i=0;i<10;i++)
	cin>>a[i];
	sort(a,a+10);
	int k;
	cin>>k;
	cout<<find(a,k)<<'\n';
 } 

这篇关于acm算法之二分查找的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!