快排和二分

快排模板：

void qs(int q[] , int l , int r){
	if(l >= r)return ;
	
	int i = l - 1 , j = r + 1 , x = q[i + j >> 1] ;
	
	while(i < j){
		while(q[++ i ] < x) ;
		while(q[-- j ] > x) ;
		if(i < j)swap(q[i] , q[j]) ;
	}
	
	qs(q , l , j ) ;
	qs(q , j + 1 , r) ;
	
}

二分查找：

对一个序列，（不一定是单调的），某个位置的左边满足某个条件但是其右边不满足那种条件，就可以用二分去查找。

在做整数二分的时候，最让人头疼的就是分段时边界条件的判断。下面记录一下我做题的思路：

举个栗子：789. 数的范围 - AcWing题库

题目大意：

​ 输出一个数字在非降序序列中出现的第一个位置和最后一个位置，若数列中没有该数字，出“-1 -1”。

思路：

​ 首先想第一个位置：k = getl(x) ：在二分时，会有一个中点mid = (l + r) / 2 。这时，目标x可能会出现在mid的左边也可能出现在mid的右边。先思考x出现在mid右边的情况：

​ 因为我们要找x的最左边的那个位置，所以我们需要一直将右边界r向左边缩：

​ 一句话，找左边，右边界向左缩

int getl(int x){
	
	int l = 1 , r = n ;
	
	while(l < r){
		int mid = l + r >> 1 ;
		
		if(x <= a[mid]) r = mid ;//右边界向左边缩
		else l = mid + 1 ;
		
	}
	return l ;
	
}

​ 其次想最后一个位置：k = getr(x)： 思路和getl类似

​ 一句话，找右边，左边界向右缩

int getr(int x){
	
	int l = 1 , r = n ;
	
	while(l < r){
		int mid = l + r + 1 >> 1;//注意l+1==r的边界情况
		
		if(a[mid] <= x) l = mid ;//l向右缩
		else r = mid - 1 ;
		
	}
	return l ;
	
}

总代码：

#include<bits/stdc++.h>
using namespace std ;
const int N = 1e6 + 10 ;

int n , m ;
int a[N] ; 

void qs(int q[] , int l , int r){
	if(l >= r)return ;
	
	int i = l - 1 , j = r + 1 ;
	int x = q[(i + j >> 1)] ;
	
	while(i < j){
		while(q[++ i ] < x) ;
		while(q[-- j ] > x) ;
		if(i < j)swap(q[i] , q[j]) ;
	}
	
	qs(q , l , j ) ;
	qs(q , j + 1 , r) ;
	
}

int getl(int x){
	
	int l = 1 , r = n ;
	
	while(l < r){
		int mid = l + r >> 1 ;
		
		if(x <= a[mid]) r = mid ;
		else l = mid + 1 ;
		
	}
	return l ;
	
}

int getr(int x){
	
	int l = 1 , r = n ;
	
	while(l < r){
		int mid = l + r + 1 >> 1;
		
		if(a[mid] <= x) l = mid ;
		else r = mid - 1 ;
		
	}
	return l ;
	
}

void solve(){
	
	int x ;
	cin>>x ;
	
	int k = getl(x) ;
	
	if(a[k] != x){
		cout<<"-1 -1\n" ;
		return ;
	}
	
	cout<<k - 1<<" "<<getr(x) - 1 <<"\n" ;
}

int main(){
	ios::sync_with_stdio(false) ;
	
	cin>>n>>m ;
	
	for(int i = 1 ; i <= n ; i ++ )cin>>a[i] ;
	
	qs(a , 1 , n ) ;//for(int i = 1 ; i <= n ; i ++ )cout<<a[i]<<" " ;cout<<endl ;
	
	while(m -- )solve() ;
	
}