©2020-2024 ioDraw All rights reserved,
Privacy Policy
<> 二分
<>前言
二分思想在我看来是将一个大的整体分成两个小的整体，在经过判断后，舍弃一个不合适的小整体，再将剩下的一个小整体一分为二，依此往复，直到找到不能再一分为二的个体。二分思想可以提高我们在做一些查找工作时的效率。
<>二分查找
下面来看一下怎样利用二分思想进行查找。
Q：在一个严格递增数列中找到一个给定的数,并返回这个数在数组中对应的下标
#include<iostream> using namespace std; //二分 //二分查找
//A[]为严格递增序列，left为二分下界，right为二分上界，x为预查询数 //二分区间为左闭右闭的区间，传入初值为[0,n-1] int
binarySearch(int A[], int left, int right, int x){ int mid;//mid为[left,
right]的中点 while(left <= right){// left > right退出 mid = (left+right)/2; if(A[mid
] == x) { return mid;//找到x就返回下标 } else if(A[mid] > x){ right = mid - 1;//向左子区间查找
} else{ left = mid + 1;//向右子区间查找 } } return -1;//没有查找成功则返回 -1 } int main(){
const int n = 10; int A[n] = {1, 3, 4, 6, 7, 8, 10, 11, 12, 15}; cout<<
binarySearch(A,0,n-1,6)<<" "<<binarySearch(A,0,n-1,9); return 0; }
如果对数组进行遍历并且找到对应的数字，时间复杂度为：O(n)
如果使用二分查找，其时间复杂度便为：O(log n)
Q：求出数列中第一个大于x的元素的位置
#include<iostream> using namespace std; //二分查找 //求出数列中第一个大于x的元素的位置 int
bigger_num(int A[], int left, int right, int x){ int mid; while(left < right){
//对于[left,right],left==right标志找到唯一位置 mid = (left + right) / 2;//中点 if(A[mid]>x){
right= mid;//向左子区间查找 }else{ left = mid+1;//向右子区间查找 } } return left;//返回最终位置 }
int main(){ const int n = 10; int A[n] = {1, 3, 4, 6, 7, 8, 10, 11, 12, 15};
cout<<bigger_num(A, 0, n-1, 6)<<" "<<bigger_num(A, 0, n-1, 9); return 0; }
<>计算根号2的值
当然二分法的运用不仅仅局限于查找，还可以用来求近似值。
Q:计算根号2的值
#include<iostream> using namespace std; //求根号2的值 const double precision = 1e-5;
//给定精度 double m(double x){//计算平方 return x*x; } double sqrt(){ double left = 1,
right= 2, mid; while(right-left > precision){ mid = (left+right)/2;//[left,
right]中点 if(m(mid)>2){//mid > 根号二 right = mid;//在左子区间继续寻找 }else{//mid < 根号二
left= mid;//在右区间进行寻找 } } return mid;//mid即为根号二的近似值 } int main(){ cout<<sqrt();
return 0; }
求得根号二的近似值为：1.41421
<>快速幂
Q：给定三个正整数a、b、m ( a < 109, b < 1018, 1 < m < 109),求ab % m
#include<iostream> using namespace std; //快速幂 //给定三个正整数a、b、m(a<10^9,
b<10^18,1<m<10^9),求a^b%m typedef long long LL; LL binaryPow(LL a, LL b, LL m){
if(b == 0) return 1;//如果b为0，那么a^0 = 1 if(b % 2 == 1) return a * binaryPow(a, b -
1, m) % m;//b为奇数，转换为b-1 else{//b为偶数，转换为b/2 LL mul = binaryPow(a, b / 2, m);
return mul * mul % m; } } int main(){ cout<<binaryPow(2, 5, 3); return 0; }
<>附：
如有错误，欢迎各位在评论区指正