快排和二分
快排模板:
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() ;
}