二分查找

· 二分查找是基于有序序列的查找算法
· 具体步骤(以严格递增序列为例):该算法一开始令[left,right]为整个序列的下标区间,然后每次测试当前[left,right]的中间位置mid=(left+right)/2;判断A[mid]与欲查询元素x的大小:
1.如果A[mid] == x,说明查找成功,退出查询
2.如果A[mid] > x,说明x在mid的左边,因此往左区间[left,mid-1]继续查找
3.如果A[mid] < x,说明x在mid的右边,因此往右区间[mid+1,right]继续查找
· 二分查找的高效之处在于每一步都可以除去当前区间中的一半元素,因此其时间复杂度为O(logn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//A[]为严格递增序列,left为二分下界,right为二分上界,x为欲查询的数
//二分区间为左闭右闭的[left,right],传入的初值为[0,n-1]
int binarySearch(int A[],int left,int right,int x){
int mid;
while(left<=right){
mid=(left+right)/2;
if(A[mid]==x) return mid;
else if(A[mid]>x){
right=mid-1;
}else{
left=mid+1;
}
}
return -1; //查找失败返回-1
}

求序列中的第一个大于等于x的元素的位置

1.如果A[mid] ≥ x,说明第一个大于等于x的元素的位置一定在mid处或mid的左侧,应往左子区间[left,mid]继续查询
2.如果A[mid] < x,说明第一个大于等于x的元素的位置一定在mid的右侧,应往右子区间[mid+1,right]继续查询

1
2
3
4
5
6
7
8
9
10
11
12
13
//A[]为递增序列,x为欲查询的数,函数返回第一个大于等于x的元素的位置
int lower_bound(int A[],int left,int right,int x){
int mid;
while(left<right){ //注意此处无= 因为此问一定有解不会查找失败,最后返回left或right均可
mid=(left+right)/2;
if(A[mid]>=x){
right=mid;
}else{
left=mid+1;
}
}
return left; //返回夹出来的最终位置
}

求序列中第一个大于x的元素的位置

1.如果A[mid]>x,说明第一个大于x的元素的位置一定在mid处或mid的左侧,应往左子区间[left,mid]继续查询
2.如果A[mid]≤x,说明第一个大于x的元素的位置一定在mid的右侧,应该往右子区间[mid+1,right]继续查询

1
2
//只需在lower_bound()函数中改变if中的判断条件
if(A[mid]>x)

解决“寻找有序序列第一个满足某条件的元素的位置”问题的固定模板

1
2
3
4
5
6
7
8
9
10
11
12
13
//二分区间为左闭右闭的[left,right],初值必须能覆盖解的所有可能取值
int solve(int left,int right){
int mid;
while(left<right){
mid=(left+right)/2;
if(条件成立){
right=mid;
}else{
left=mid+1;
}
}
return left;
}

二分法拓展

快速幂

1
2
3
4
5
6
7
8
9
10
11
typedef long long LL;
//求a^b%m,递归写法
LL binaryPow(LL a,LL b,LL m){
if(b==0) return 1;
//b为奇数,转换为b-1
if(b%2==1) return a*binaryPow(a,b-1,m)%m;
else{
LL mul=binaryPow(a,b/2,m);
return mul*mul%m;
}
}