Question

编程C++二分查找

给定一列有序的数。查询其中第一个大于x的数的位置。位置下标从0开始。如果这列数中不存在大于x的数，则输出-1。
Input
每组输入由四行组成，第一行一个整数N(1≤N≤10,000)，表示这列数是N。第二行有N个由空格隔开的数，表示这列有序的数。第三行一个整数Q(1≤N≤10,000)，表示有Q次查询。第四行有Q个由空格分开的整数，表示查询第一个大于这个数的位置。
Output
输出Q个整数，回答Q次查询。这Q个整数由每20个一行，由空格分开。
Sample Input
7
10 10 20 20 20 30 30
2
15 25
Sample Output
2 5

Answer 1

#include <iostream>
using namespace std;
int main()
{
int i,j,m=0,n=0,high=0,low=0,mid=0;
cin>>m;
int *data=new int[m];
for(i=0;i<m;i++)
cin>>data[i];
cin>>n;
int *find=new int[n];
int *location=new int[n];
for(i=0;i<n;i++)
{
cin>>find[i];
location[i]=-1;
}
for(i=0;i<n;i++)
{
low=0;high=m;
while(low<=high){//二分查找
mid=(low+high)/2;
if(data[mid]>find[i]&&data[mid-1]<=find[i])
{location[i]=mid;break;}
else if(data[mid]>find[i]&&data[mid-1]>find[i])
high=mid-1;
else if(data[mid]<find[i])
low=mid+1;
}
continue;//查找下一个
}
for(i=0;i<n;i++)
cout<<location[i]<<" ";
cout<<endl;

system("pause");
return 0;
}

Answer 2

#include <stdio.h>
#define MAXN 1000
#define MAXQ 1000

int main()
{
int i,N,Q;
int data[MAXN],query[MAXQ],index[MAXQ];

scanf("%d",&N);
for (i=0;i<N;i++)
scanf("%d",&data[i]);
scanf("%d",&Q);
for (i=0;i<Q;i++)
scanf("%d",&query[i]);

/* printf("====\nN=%d\tQ=%d\n",N,Q);
for (i=0;i<N;i++)
printf("%d ",data[i]);
printf("\n");
for (i=0;i<Q;i++)
printf("%d ",query[i]);
printf("\n"); */

for (i=0;i<Q;i++)
{
int mid;
int left=0,right=N-1;
if (query[i]>=data[right])
{
index[i]=-1;
continue;
}
while (right-left>1)
{
mid=(left+right)/2;
/*printf("left=%d,mid=%d,right=%d\n",left,mid,right);*/
if (query[i]>data[mid])
left=mid;
else
right=mid;
}
if (query[i]>data[left])
index[i]=right;
else
index[i]=left;
}
for (i=0;i<Q;i++)
if (i%20!=19)
printf("%d ",index[i]);
else
printf("%d\n",index[i]);
return 0;
}

Answer 3

二分查找示例:

public static int GetIndex(int[] a, int num, int startIndex, int endIndex)
{
int index = (startIndex + endIndex) / 2;
//如?果?找ò不?到?返う?回?-1
if (startIndex > endIndex)
{
return -1;
}
if (a[index] == num)
{
return index;
}
else
{
if (num < a[index])
{
return GetIndex(a, num, startIndex, index - 1);
}
else
{
return GetIndex(a, num, index + 1, endIndex);
}

}

}