无重复的二分搜索算法

本文关键字:二分 搜索算法 | 更新日期: 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)