二分查找
时间: 1ms 内存:128M
描述:
输入不多于20个升序排列的整数,以及一个待查找的数key,输出key在序列中的位置(从0开始计位序)。查找采用二分查找的方法进行,请将下面的程序补充完整。
#include <iostream>
using namespace std;
const int SIZE=20;
int binary_search(int arr[], int n, int k);
int main()
{
int d[SIZE];
int index, key, num=0;
cin>>key;
while(cin>>d[num])
num++;
index = binary_search(d, num, key);
if(index >= 0)
cout<<index<<endl;
else
cout<<"NO"<<endl;
return 0;
}
//提交全部程序代码
int binary_search(int arr[], int n, int k)
{
int i=-1;
int low=_____(1)_____,high=_____(2)_____,mid;
while(low<=high)
{
mid=______(3)________;
if(arr[mid]==k)
{
i=mid;
break;
}
else if(_____(4)_____)
high=mid-1;
else
_______(5)__________;
}
return i;
}
输入:
先输入要查找的数
下一行输入升序排列的若干整数(不超过20个),以CTRL-Z结束
输出:
若要查找的数在序列中,输出其在序列中的位置(从0开始计数),若不能找到,输出NO
示例输入:
45
23 36 45 76 81 88 89 91
示例输出:
2
提示:
参考答案:
文章评论