956 二分查找

Description

有n(1<=n<=1000005)个整数，已经按照从小到大顺序排列好，现在另外给一个整数x，请找出序列中第1个大于x的数的下标！

Input

输入数据包含多个测试实例，每组数据由两行组成，第一行是n和m，第二行是已经有序的n个数的数列。n和m同时为0标示输入数据的结束，本行不做处理。

Output

对于每个测试实例，请找出序列中第1个大于x的数的下标！。

Sample Input

3 3
1 2 4
0 0

Sample Output

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <stdio.h>
 4 #include <math.h>
 5 #include <string.h>
 6 #include <time.h>
 7 using namespace std;
 8 int a[1000010];
 9 int main()
10 {
11     int n,m,first,last,mid;
12     while(cin>>n>>m&&(n!=0&&m!=0))
13     {
14         memset(a,0,sizeof(a));
15         for(int i=0;i<n;i++)
16         scanf("%d",&a[i]);
17         first=0;last=n-1;mid=0;
18         while(first<=last)
19         {
20             mid=(first+last)/2;
21             if(a[mid]<m&&a[mid+1]>m)
22             break;
23             if(a[mid]<m)
24             first=mid+1;
25             else
26             last=mid;
27         }
28         cout<<mid+1<<endl;
29     }
30     return 0;
31 }

View Code