二分法查找

AngelNH

发布于 2020-04-14 18:35:27

6270

发布于 2020-04-14 18:35:27

文章被收录于专栏：AngelNI

二分法查找

例如：

给一有序的数组a[9]={1,2,3,4,5,6,7,8,9,}，想要确定 3 的位置。

实现：

(a[0]+a[8])/2=5   大于  3		则只需要查找a[0]~a[4]就可以
(a[0]+a[4])/2=3   此时刚好等于3，则此时3的位置就是（0+4）/2=2
则可知 a[2]=3    至此查找结束

下面通过一个例子来具体体验下二分法的妙处

Trailing Zeroes

n的阶乘尾部有q个连续的0，现在给你q，请你算出满足条件的n，如果有多个n满足条件，输出最小的那个即可。

Input

输入一个T(T <= 10000),表示样例数量。

每个样例输入一个q。(1 <= q <= 100,000,000)

output

对于每个样例，输出满足条件的最小的n，如果没有满足条件的则输出”impossible”。.

Sample Input

Sample Output

Case 1: 5

Case 2: 10

Case 3: impossible

思路

这是一个判断阶乘后面有多少个零，输出满足条件下的最小解。

首先判断0的个数，我们可以通过判断5的个数来判断0`的个数（10可以分成2*5）

例如：5！=1*2*3*4*5=120

代码实现

long long fn(long long n)   //求n阶乘的末尾0个数 
{
	long long a = 0;
	while(n)
	{
		a += n/5;
		n = n/5;
	}
	return a;
}

例如：判断25！末尾有几个0

a=25/5 –> a=5

a+=5/5 –> a=6

由此可以判断25的阶乘末尾有6个零（拿计算器验证）

整个题解

（这是大佬写的，我偷偷拿来哈~）

##### #include<iostream>  //cin，cout数据流输入输出的头文件

#include<cstdio>
using namespace std;
typedef long long ll;  //声明定义long long 的别名 ll
const ll maxn = 1e17;  //题目中0的个数  1~1e9

ll fn(ll n)//求n阶乘的末尾0个数 
{
	ll a = 0;
	while(n)
	{
		a += n/5;
		n = n/5;
	}
	return a;
}

int main()
{
	int n, q;
	ll ans;//定义所要求的答案
	int Case = 0;
	cin>>n; //输入测试组数
	while(n--)
	{
		Case++;//判断测试第几个
		cin>>q;//输入0的个数
		int l, r;//定义左值，和右值
		l =1;
		r = maxn;
		ans = 0;
		while(r>=l)
		{
			ll mid = (l+r)>>1; //直接平均可能溢出，所以用这个  注： >> 值的二进制形式右移一位，相当于十进制除2
			if(fn(mid)==q)
			{
				ans = mid;//如果中间的那个数零的个数恰好等于q，则为答案
				r = mid-1;
			}
			else if(fn(mid)<q) l = mid+1;//如果中间的值0的个数小于q，则左值++
			else r = mid-1;//  否则 右值——
		}
		if(ans) printf("Case %d: %lld", Case, ans);//如果结果不为零，按输出格式打印
		else printf("Case %d: impossible", Case);//否则，则输出impossile
		cout<<endl;
	}
	
	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019-06-20|，如有侵权请联系 cloudcommunity@tencent.com 删除

input