二分查找

二分查找

时间: 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

提示:

参考答案(内存最优[556]):

program p1000(Input,Output); 
var 
	a,b,i,mark:integer;
begin 
	read(a);
	while not eof(input) do
		begin
		read(b);
		if b=a then
			mark := i;
		i := i+1;
		end;
	if mark = 0 then
		write('NO')
	else
		write(mark);
end.

参考答案(时间最优[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=0,high=n-1,mid;
    while(low<=high)
    {
        mid=(low+high)/2;
        if(arr[mid]==k)
        {
            i=mid;
            break;
        }
        else if(arr[mid]>k)
            high=mid-1;
        else
            low=mid+1;
    }
    return i;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注