二分查找

发布时间 2023-07-23 09:47:15作者: So_noGeirf

二分n个数找k是第几个(k有多个,输出第一个,如果不存在输出-1):

如数列:$2$ $7$ $9$ $1$ $3$ $5$ $6$ $2$ $3$

二分要保证:

  • 有序(若无序先排序),满足单调性
  • 数列单调不降

Sort后:$1$ $2$ $2$ $3$ $3$ $5$ $6$ $7$ $9$

#include<iostream>
using namespace std;
int main(){
	int a[10]={0,1,2,2,3,3,5,6,7,9};
	int l=1,r=9,mid,ans,k=8;
		while(l<=r){
			mid=(r+l)/2;
			if(k<=a[mid]) r=mid-1,ans=mid;
	      else l=mid+1;
		}
		if(a[ans]==k) cout<<ans;//注意判断
		else cout<<"404 No Found!"<<endl;
	return 0;
}