二分法-学习笔记

玩家A从一个范围中选择一个数，然后让玩家B猜这个数字
经典问题：如何在一个严格递增序列A中找出给定的数x。
1.线性扫描序列中的所有元素
2.二分查找，基于有序序列的查找算法，假设严格递增序列，该算法一开始令[left,right]为整个序列的下标区间，然后每次测试当前[left,right]的中间位置mid=(left+right)/2，判断A[mid]与预查询的元素x的大小：
if A[mid]=x，查找成功，break
if A[mid]>x，说明元素x在mid位置的左边，因此往左子区间[left,mid-1]继续查找
if A[mid] 注意：二分查找的过程与序列的下标从0开始还是从1开始无关
【非递归：】

#include 
#include 
using namespace std;
//x为预查询的数 
int x,n; 
const int maxn=110;
int A[maxn];
int binarySearch(int A[],int left,int right,int x){
	int mid;
	sort(A,A+n);
	while(left<=right){
		mid=(left+right)/2;
		if(A[mid]==x){
			return mid;	//找到x，返回下标
		} 
		else if(A[mid]>x){	//x在left~mid-1内 
			right=mid-1; 
		} else{ 		//x在mid+1~right内 
			left=mid+1;
		}
	}
	return -1; 	//未查询到
}
int main(){
	printf("请输入要排列的个数："); 
	scanf("%d",&n); 
	printf("请输入**不含重复数字**的数组A=");
	for(int i=0;i 
如果递增序列中的元素可能重复，那么如何对给定的欲查询元素x，求出序列中第一个大于等于x的元素的位置L以及第一个大于x的元素的位置R？如：{1，3，3，3，6}中，查询3，应当得到L=1,R=4；如果查询5，应当得到L=R=4；如果查询6，应当得到L=4,R=5；查询8，得L=R=5。如果序列中没有x，那么L和R也可以理解为假设序列中存在x，则x应当在的位置。
 
//函数返回第一个大于等于x的元素的位置 
int lower_bound(int A[],int left,int right,int x){
	int mid;
	while(left=x){ 	//中间的数大于等于x 
			right=mid; 		//往左子区间查找 
		}else{
			left=mid+1;
		}
	}
	return left;
}
//函数返回第一个大于x的元素的位置
int upper_bound(int A[],int left,int right,int x){
	int mid;
	while(leftx){ 	//**中间的数大于x**
			right=mid; 		//往左子区间查找 
		}else{
			left=mid+1;
		}
	}
	return left;
} 

 
解决“寻找有序序列第一个满足某条件的元素的位置”问题的固定模板：
 二分区间为【左闭右闭】
 
int solve(int left,int right){
	int mid;
	while(leftmid 
			left=mid+1;
		}
	}
	return left; 
}
 
二分区间为（ 左开右闭 】
 
int solve(int left,int right){
	int mid;
	while(left+1mid 
			left=mid;
		}
	}
	return right; 
}
 
另：如果想寻找最后一个满足“某条件”的元素的位置，则可以先求第一个满足“！某条件”的元素的位置，然后将该位置-1即可。
 
二分法拓展 
计算√2的近似值。（设精度10-5 ，eps=1e-5）
 f(x)=x2 ,x在[1,2]范围内，fx随着x的增大而增大。
 令浮点型left和right的初值分别为1和2，然后根据left和right的中点mid处f(x)的值与2的大小来选择子区间进行逼近：
 ·if f(mid)>2,说明mid>√2,应当在[left,mid]范围内继续逼近，故令right=mid;
 ·if f(mid)<2,说明mid<√2,应当在[mid,right]的范围内继续逼近，故令left=mid;
 
#include 
#include 
#include 
using namespace std;
#define eps 1e-5		//精度为10^5
//写一个函数，计算f(x)=x^2 
double f(double x){ 		
	return x*x; 
} 
//二分法求近似值 
double calSqrt(){
	double left=1,right=2,mid;
	while(right-left>eps){
		mid=(left+right)/2;
		if(f(mid)>2){
			//右边超出，往左逼近
			right=mid; 
		}else{
			//往右逼近 
			left=mid;
		}
	}
	return mid;
}
int main(){
	 
	printf("近似值为%lfn",calSqrt());
}
 
问题转换：给定一个定义在[L,R]上的单调函数f(x)，求方程f(x)=0的根
 1.如果f(mid)>0，说明f(x)=0的根在mid左侧，应往左子区间[left,mid]继续逼近，即令right=mid；
 2.如果f(mid)<0，说明f(x)=0的跟在mid右侧，应往右子区间[mid,right]继续逼近，即令left=mid；
 当rigth-left<10-5 时，表明达到精度要求，结束算法，返回的当前mid值即为f(x)=0的根。
 
//二分法求f(X)=0 
double solve(double L,double R){
	double left=L,right=R,mid;
	//未达到精度要求 
	while(right-left>eps){ 		
		mid=(left+right)/2;
		if(f(mid)>0){ 	//f(X)递增时，f(mid)>0;递减，f(mid)<0 
			//右边超出，往左逼近
			right=mid; 
		}else{
			//往右逼近 
			left=mid;
		}
	}
	//达到精度要求，返回近似值 
	return mid;
}
 
快速幂 
给定三个正整数a<109、b<106、19，求ab %m
 
typedef long long LL; 	//为复杂的数据类型定义简单的别名
//防止两个int型变量相乘后溢出 
LL pow(LL a,LL b,LL m){
	LL ans=1;
	for(int i=0;i 
若改为b<1018，使用快速幂的做法
 1.如果b是奇数，有ab =a*ab-1 .
 2.如果b是偶数，有ab=ab/2 *ab/2 .
 用到递归思想，快速幂的递归写法，时间复杂度为O(logb):
 
typedef long long LL; 	//为复杂的数据类型定义简单的别名
//求a^b%m，递归写法
LL binaryPow(LL a,LL b,LL m){
	//递归出口 
	if(b==0) return 1;	//a^0=1
	//b为奇数 
	if(b%2==1){ //可也写成b&1
		return a*binaryPow(a,b-1,m)%m;
	} else{ 	//b为偶数 
		LL mul = binaryPow(a,b/2,m);
		return mul*mul%m;
	}
} 
 
快速幂的迭代写法：
 a13 ,13的二进制1101，13=23+22+20=8+4+1，a13=a8+4+1=a8*a4 *a1 。
 即，如果b的二进制的i号位为1，那么项a的2i次方就被选中。
 于是可以得到计算ab的大致思路：令i从0到k枚举b的二进制的每一位，如果当前位为1，那么累积a的2i次方。
 具体实现：
 1.初始令ans=1，用来存放累积的结果
 2.判断b的二进制末尾是否为1，即b&1是否为1，b是否为奇数
 3.令a平方，并将b右移一位
 4.只要b大于0，就返回2
 
typedef long long LL;
//求a^b%m，迭代写法
LL binaryPow(LL a,LL b,LL m){
	LL ans=1;
	while(b>0){
		if(b&1){
			ans=ans*a%m;
		}
		a=a*a%m;
		b>>=1;	//b的二进制右移一位，b=b>>1或b=b/2 
	}
	return ans;
}