首页 > 程序开发 > 软件开发 > 其他 >

二分查找

2017-03-29

二分查找:给出含有n个数的升序序列,保证序列中的数两两不相等,这n个数编号从1 到n。

二分查找:给出含有n个数的升序序列,保证序列中的数两两不相等,这n个数编号从1 到n。

然后给出q次询问,每次询问给出一个数x,若x存在于此序列中,则输出其编号,否则输出-1。

单组输入。首先输入一个整数n(1 <= n && n <= 3000000),接下的一行包含n个数。

再接下来的一行包含一个正整数q(1 <= q && q <= 10000),表示有q次询问。

再接下来的q行,每行包含一个正整数x。

对于每次询问,输出一个整数代表答案。

#include

#include

using namespace std;

int a[3000000];

void search(int x,int bot,int top);

int main()

{

int n,p,x,i;

while(cin>>n)

{

for(i=1;i<=n;i++)

//cin>>a[i];

scanf("%d",&a[i]);

//cin>>p;

scanf("%d",&p);

for(i=1;i<=p;i++)

{

//cin>>x;

scanf("%d",&x);

search(x,1,n);

}

}

}

void search(int x,int bot,int top)

{

int mid;

mid=(bot+top)/2;

if(bot<=top)

{

if(x==a[mid])

//cout< printf("%d\n",mid);

else if(x search(x,bot,mid-1);

else

search(x,mid+1,top);

}

else

//cout<<"-1"< printf("%d\n",-1);

}

cin cout超时

就改了scanf printf

二分法就是一个有序的序列

top代表最顶端,bot代表最低端,mid代表中间的位置

mid=(top+bot)/2

相关文章
最新文章
热点推荐