请实现有重复数字的有序数组的二分查找。
输出在数组中第一个大于等于查找值的位置,如果数组中不存在这样的数,则输出数组长度加一。
输入格式:
输入第一行有两个数,第一个数为数组长度n(≤10^6),第二个数为需要查找的数。
接下来有n个整数,以空格或换行符分隔。
输出格式:
输出待查找的数的位置。
输入样例:
5 4
1 2 4 4 5
输出样例:
3
样例解释:
有5个数,查找4出现的位置,4第一次出现在第3个位置,所以输出3。
#include <bits/stdc++.h>
using namespace std;
int Zheban(int a[],int low,int high,int k)
{
while (low < high)
{
int mid = (low + high-1) / 2;
if (k > a[mid])
low = mid + 1;
else
high = mid;
}
if (k == a[high])
{
return high;
}
return -1;
}
int main()
{
int a[1000001];
int size1 = 0;
int number = 0;
int i,j=0;
cin >>size1>>number;
for(i=1;i<=size1;i++)
{
cin >>a[i];
}
j=Zheban(a,1,size1,number);
if(size1==0)cout<<1;
else if(size1<0&&size1>1000001)cout<<1;
else if(j>=0)cout<<j;
else cout<<size1+1;
}