二分查找

#include <bits/stdc++.h>
using namespace std;
int main() {

	return 0;
}

//如果存在x  这个函数返回1  否则返回0  
int bs(int x){//查找数字x  在a数组当中有没有出现过 
	int l=1,r=n;
	while(l<=r){
		int m=(l+r)/2;//mid  
		if(a[m]==x) return 1;
		if(a[m]>x) r=m-1;
		if(a[m]<x) l=m+1;
	} 
	return 0;
}
//查找数字x第一次出现的位置 
int bs2(int x){//查找数字x  在a数组当中有没有出现过 
	int l=1,r=n,ans=-1;//细节1：左右指针的初始值 
	while(l<=r){//细节2：while循环里面的条件一定是 l<=r 
		int m=(l+r)/2;//mid  
		if(a[m]==x) ans=m,r=m-1;
		if(a[m]>x) r=m-1;//细节3：仔细思考指针是怎么样移动的 
		if(a[m]<x) l=m+1;
	} 
	return ans;
}
//查找数字x最后一次出现的位置 
int bs3(int x){//查找数字x  在a数组当中有没有出现过 
	int l=1,r=n,ans=-1;//细节1：左右指针的初始值 
	while(l<=r){//细节2：while循环里面的条件一定是 l<=r 
		int m=(l+r)/2;//mid  
		if(a[m]==x) ans=m,l=m+1;
		if(a[m]>x) r=m-1;//细节3：仔细思考指针是怎么样移动的 
		if(a[m]<x) l=m+1;
	} 
	return ans;
}
//我们结合bs2和bs3 可以帮助我们快速的查找某个数字在 数组里面一共出现了多少次
6---> 1 2 3 4 5 6 
//查找大于x  第一次出现的位置 
int bs4(int x){
	int l=1,r=n,ans=-1;
	while(l<=r){
		int m=(l+r)/2;
		if(a[m]>x) ans=m,r=m-1;
		else l=m+1;
	}
	return ans;
}
//查找大于等于x  第一次出现的位置 
int bs5(int x){
	int l=1,r=n,ans=-1;
	while(l<=r){
		int m=(l+r)/2;
		if(a[m]>=x) ans=m,r=m-1;
		else l=m+1;
	}
	return ans;
}
//查找小于x  最后一次出现的位置
int bs6(int x){
	int l=1,r=n,ans=-1;
	while(l<=r){
		int m=(l+r)/2;
		if(a[m]<x) ans=m,l=m+1;
		else r=m-1;
	}
	return ans;
}
//查找小于等于x  最后一次出现的位置
int bs7(int x){
	int l=1,r=n,ans=-1;
	while(l<=r){
		int m=(l+r)/2;
		if(a[m]<=x) ans=m,l=m+1;
		else r=m-1;
	}
	return ans;
}
//结合bs5和bs7  可以快速的计算在数组中 L到R这段范围内的数字有多少个