1 引言
在二分查找(英语:binary search),也称折半搜索(英语:half-interval search)、对数搜索(英语:logarithmic search),是用来在一个有序数组中查找某一元素的算法。
二分法的运用原理:以在一个升序(递增的序列)数组中查找一个数为例,每次考察数组当前部分的中间元素,如果中间元素刚好是要找的,就结束搜索过程;如果中间元素小于所查找的值,那么左侧的只会更小,不会有所查找的元素,只需到右侧查找;如果中间元素大于所查找的值同理,只需到左侧查找。
2 问题描述
图2.1
3 算法描述
通过评测用例规模可以知道,问题时间复杂度为N(109),不能直接暴力解决,那么就需要寻找规律,利用其它算法解答。
根据杨辉三角定义可知,其数值是二项式系数(组合数)在三角形中的几何排列(n的数值为第n行),根据题目要求可知,输出答案为第一次出现的位置,根据图3.1可知,只需求解左半部分即可。
图3.1
(3)根据观察图3.1可知,每一个斜行是依次递增,同时再横向观察可知,组合数越靠近中间,数值越大,那么同理可得,位置越靠下方,数值便越大,因此,在解决此问题时,应该从下方开始寻找,同时可知,第1斜行的1=C(0,0),第二斜行的2=C(2,1),第三斜行的6=C(4,2),第四斜行的20=C(6,3),那么第i斜行的起始位置 =C(2n,n),同理,根据计算可知C(34,17)= 2×109 而C(32,16)< 108所以可以从16行开始枚举,枚举到相对于所求值小但大于下一斜行起始值,找到斜行起始值,开始使用二分法查找,因为斜行满足递增序列。
(4)寻求的位置,可以在查找的时候确定,N所在行 n和所在斜行 k ,然后通过等差公式 n*(n+1)/2 计算它之前数目的个数再加上 k+1。
(5)例如:输入整数N = 15,开始从16行枚举,只需枚举到第3斜行起始值 = 6, k = 2 ,开始二分斜行,得到实际行n = 6,因此需要k+1,结果 ans = 6*(6+1)/2 + 2 + 1 = 24。
4 代码
n = int(input()) def C(a,b): #求组合数 res = 1 i = a for o in range(1,b+1): res = res *i / o i -=1 if res > n: return res return res def check(k): #二分查找(需要找到边界值) #左边界2k,右边界为max(l, n)取二者最大,避免右边界小于左边界 left = 2*k right = max(n,left) while left < right: mid = left + right >> 1 if C(mid,k) >= n: right = mid else: left = mid + 1 if C(right,k) != n: return False print(int((right+1)*right//2+k+1)) return True k = 16 for i in range(k): k -=1 if(check(k)): break
5 结语
通过解答简单的示列问题,可以充分了解到二分算法的基本原理以及思考问题的思路。