二分查找下界(c++题解)

题目描述

在一个N个元素的不递减数列中，查找大于或等于X的第一个位置，如果找不到则输出n+1。下标范围从1~N。

输入格式

共3行

第一行一个n (1 ≤ n ≤ 1000000)

第二行n个不递减的整数

第三行查找目标数x

数据都在int范围内

输出格式

第一个大于等于x的数的下标，没有则输出n+1

样例

样例输入1

复制5
1 3 3 3 4
3

样例输出1

复制2

样例输入2

复制5
1 3 3 3 4
8

样例输出2

复制6_______________________________________________________________________________________日常发作业题解。 

一开始竟然写成冒泡了，呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜

也是简单爆爆爆爆爆爆爆爆爆爆爆爆爆爆爆爆爆爆爆爆爆爆爆爆爆爆爆爆爆爆爆爆爆爆爆表的题

写作不易，点个赞呗!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 

_____________________________________________________________________________

#include <bits/stdc++.h>
using namespace std;
long long a[10000005],n,mid,m; 
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	cin>>m;
	int l=1,r=n;
	while(l<r){
		mid=(l+r)/2;
		if(a[mid]>=m)r=mid;
        else l=mid+1;
	}
	if(a[l]<m)cout<<n+1;
	else cout<<l;
}