本文主要是介绍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算法之二分查找的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!