《算法笔记》4.5小节——算法初步->二分
2020-04-08 本文已影响0人
木子李_0961
@[TOC]
Contest100000583 - 《算法笔记》4.5小节——算法初步->二分
4.5 二分理论与例题
4.5.1 二分查找
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
//二分查找基础代码
#include <stdio.h>
//二分查找求序列中第一个大于等于x的元素的位置
int lower_bound(int A[],int left,int right,int x)
{
int mid;
while(left<right)
{
mid = (left+right)/2;
if(A[mid] >= x)//若中间值大于等于x，则第一个大于等于x的元素可能在mid或之前取到
{
right = mid;
}
else//否则大于等于x的第一个元素在mid之后取到
{
left = mid + 1;
}
}
return left;
}
//二分查找求序列中第一个大于x的元素的位置
int upper_bound(int A[],int left,int right,int x)
{
int mid;
while(left<right)
{
mid = (left+right)/2;
if(A[mid] > x)//若中间值大于x，则第一个大于等于x的元素可能在mid或之前取到
{
right = mid;
}
else//否则大于等于x的第一个元素在mid之后取到
{
left = mid + 1;
}
}
return left;
}
int binarySearch(int A[],int left,int right,int x)
{
int mid;
while(left <= right)
{
mid = (left+right)/2;//为防止溢出，等价语句：mid = left+(right-left)/2
if(A[mid] == x) return mid;
else if(A[mid] > x)//中间的数大于x，则在左侧查找
{
right = mid-1;
}
else//中间的数小于x，则在右侧查找
{
left = mid+1;
}
}
return -1;//查找失败
}
int main()
{
const int n = 10;
int A[n] = {1,3,4,6,7,8,10,11,12,15};
printf("%d %d\n",binarySearch(A,0,n-1,6),binarySearch(A,0,n-1,9));
return 0;
}
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
4.5.2 二分法拓展
//二分拓展——装水问题
#include <cstdio>
#include <cmath>
const double PI = acos(-1.0);
const double eps = 1e-5;
double f(double R,double h)//获得面积比例函数
{
double alpha = 2*acos((R-h)/R);
double L = 2*sqrt(R*R - (R-h)*(R-h));
double S1 = alpha * R * R/2 - L *(R-h)/2;
double S2 = PI*R*R/2;
return S1/S2;
}
double solve(double R,double r)
{
double left = 0,right = R,mid;
while(right - left > eps)
{
mid = (left+right)/2;
if(f(R,mid) > r)
{
right = mid;
}
else
{
left = mid;
}
}
return mid;
}
int main()
{
double R,r;
scanf("%lf%lf",&R,&r);
printf("%.4f\n",solve(R,r));
return 0;
}
4.5.3 快速幂
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
//二分—快速幂
typedef long long LL;
LL binaryPow(LL a,LL b,LL m)
{//求a^b%m迭代写法
LL ans = 1;
while(b>0)
{
if(b&1)//如果b的二进制末尾为1，即为奇数
{
ans = ans * a % m ;
b>>=1;//b二进制右移一位
}
}
return ans;
}
Codeup习题练习
1934 Problem A 找x
http://codeup.cn/problem.php?cid=100000585&pid=0
//1934 Problem A 找x
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
struct elem//结构体存储原来的序号与数值，尝试用二维数组不成功
{
int value;
int oldindex;
};
bool cmp(elem a,elem b)//比较规则
{
return a.value<b.value;
}
int binarySearch(elem A[],int left,int right,int x)//二分查找函数
{
int mid;
while(left<=right)
{
mid = (left+right)/2;
if(A[mid].value == x)
{
return mid;
}
else if(A[mid].value > x)
{
right = mid - 1;
}
else
{
left = mid + 1;
}
}
return -1;
}
int main()
{
int n;
while(cin>>n)
{
elem nums[n];
for(int i=0;i<n;i++)
{
cin>>nums[i].value;
nums[i].oldindex = i;
}
sort(nums,nums+n,cmp);
int x;
cin>>x;
int ind = binarySearch(nums,0,n-1,x);
if(ind == -1)
cout<<-1<<endl;
else
cout<<nums[ind].oldindex<<endl;
}
return 0;
}
1936 Problem B 打印极值点下标
题目链接：http://codeup.cn/problem.php?cid=100000585&pid=1
//1936 Problem B 打印极值点下标
//版本一：通过OJ
#include <iostream>
#include <cstdio>
using namespace std;
bool Judge(int A[],int i)
{
if(A[i]>A[i-1]&&A[i]>A[i+1] || A[i]<A[i-1]&&A[i]<A[i+1])
return true;
else
return false;
}
int main()
{
int n;
// int num[85] = {0};
while(cin>>n)
{
while(n--)
{
int flag=false; ///设置一个标志变量来控制空格的输出
int elenum;
cin>>elenum;
int num[elenum];//k个整数
for(int i=0;i<elenum;i++)
{
cin>>num[i];
}
if(num[0] != num[1])
{
cout<<0;
flag = true;
}
for(int i=1;i<elenum-1;i++)
{
if(flag && Judge(num,i))
cout<<' '<<i;
else if(Judge(num,i))
{
cout<<i;
flag = true;
}
}
if(num[elenum-1] != num[elenum-2])
{
if(flag)
{
cout<<' '<<elenum-1;
flag = true;
}
else
cout<<(elenum-1);
}
if(flag)
cout<<endl;
}
}
return 0;
}
下面为题1936版本2：未通过OJ
//1936 Problem B 打印极值点下标
//难点在于空格输出格式的限制
//1936版本2：未通过OJ
#include <iostream>
#include <cstdio>
using namespace std;
bool Judge(int A[],int i)
{
if(A[i]>A[i-1]&&A[i]>A[i+1] || A[i]<A[i-1]&&A[i]<A[i+1])
return true;
else
return false;
}
int main()
{
int n;
while(cin>>n)
{
while(n--)
{
int elenum;
cin>>elenum;
int num[elenum];//k个整数
int res[elenum]={0}; //记录下标
int res_cnt=0;
for(int i=0;i<elenum;i++)
{
cin>>num[i];
}
if(num[0] != num[1])
{
res[res_cnt++] = 0;
}
for(int i=1;i<elenum-1;i++)
{
if(Judge(num,i))
{
res[res_cnt++] = i;
}
}
if(num[elenum-1] != num[elenum-2])
res[res_cnt++]=elenum-1;
for(int i=0;i<res_cnt-1;i++)
{
cout<<res[i]<<" ";
}
cout<<res[res_cnt-1]<<endl;
}
}
return 0;
}
1937 Problem C 查找
题目链接：http://codeup.cn/problem.php?cid=100000585&pid=2
//1937 Problem C 查找
//注意二叉查找需要数组有序，sort的应用
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int binarySearch(int A[],int left,int right,int x)
{
int mid;
while(left<=right)
{
mid = (right+left)/2;
if(A[mid] == x)
return mid;
else if(A[mid]>x)
{
right = mid - 1;
}
else
left = mid + 1;
}
return -1;
}
int main()
{
int n;//输入数组长度
while(cin>>n)//输入有多组数据
{
int a[n];//输入数组
for(int i=0;i<n;i++)
{
cin>>a[i];
}
sort(a,a+n);
int m;//输入查找个数
cin>>m;
while(m--)
{
int num;//输入的查找数字
cin>>num;
int id = binarySearch(a,0,n-1,num);
if(id==-1)
{
cout<<"NO"<<endl;
}
else
{
cout<<"YES"<<endl;
}
}
}
return 0;
}
总结下：
二分法的思想与模式较为固定，二分查找代码熟悉，cmp的规则定好，注意二分查找前提是数组有序
