二分查找

#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这段范围内的数字有多少个 

进制转换

string tentod(int n,int d){//十进制转d进制
	if(n==0)return "0";
	string s;
	while(n){
		int t=n%d;
		char c;
		if(t<=9){
			c=char(t+'0');
		}else{
			c=char(t-10+'A');
		}
		s=c+s;
		n/=d;
	}
	return s;
}

int dtoten(string s,int d){d进制转10进制
	int sum=0,w=1;
	for(int i=s.size()-1;i>=0;i--){
		int x;
		if(s[i]>='0'&&s[i]<='9'){
			x=s[i]-'0';
		}else{
			x=s[i]-'A'+10;
		}
		sum+=x*w;
		w*=d;
	}
	return sum;
}