无重复的二分搜索算法
本文关键字:二分 搜索算法 | 更新日期: 2023-09-27 17:51:25
我正在尝试编写一个函数,该函数将允许在二进制搜索模式中处理从0-n的所有数字,而不重复。
这里有一个我想要的例子:
get(bigint max, bigint point)
get(10000, 0) = 0 //start
get(10000, 1) = 10000 //end
get(10000, 2) = 5000 //middle
get(10000, 3) = 2500 //(max/4) * 1
// Skip 500 as we've already done that one
get(10000, 4) = 7500 //(max/4) * 3
get(10000, 5) = 1250 //(max/8) * 1
// Skip 250 as we've already done it
get(10000, 6) = 3750 //(max/8) * 3
// Skip 500 as we've already done that one
get(10000, 7) = 6250 //(max/8) * 5
// Skip 750 as we've already done that one
get(10000, 8) = 8750 //(max/8) * 7
我认为这是一个启发,因为所有的乘数都是奇数,通过使用2的幂作为除数。
我如何才能最有效地做到这一点,因为几乎所有的数字都将是大整数?
这是一个算法(伪代码)
function get(max, point)
if point == 0 then
return 0
if point == 1 then
return max
x = 2*point-1
y = high_power_of_two(x) // e.g., high_power_of_two(13) == 8
return (x-y)*(max/y)