前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >二分法查找

二分法查找

作者头像
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 的位置。

实现:
代码语言:javascript
复制
(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
代码语言:javascript
复制
输入一个T(T <= 10000),表示样例数量。

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

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

Sample Input
代码语言:javascript
复制
3

1

2

5
Sample Output
代码语言:javascript
复制
Case 1: 5

Case 2: 10

Case 3: impossible

思路

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

首先判断0的个数,我们可以通过判断5的个数来判断0`的个数(10可以分成2*5)

代码语言:javascript
复制
例如:5!=1*2*3*4*5=120
代码实现
代码语言:javascript
复制
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个零(拿计算器验证)

整个题解

(这是大佬写的,我偷偷拿来哈~)

代码语言:javascript
复制
##### #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 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 二分法查找
  • Trailing Zeroes
    • 思路
      • 整个题解
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档