修改二进制搜索以获得更好的性能

Modifying Binary Search to obtain better performances

尝试的解决方案：(1) 假设 x 是奇数。我们将搜索集减少了一半。在最坏的情况下，复杂度现在是 log(n / 2) = logn - 1。现在我们简单的对奇数进行二分查找

我不确定这个解决方案是否正确，因为我不知道解决此类问题的一般方法。我将不胜感激所有 3 个部分的解决方案。如果我没有迷路，我肯定会尝试更多的问题。在发布之前我已经尝试过提前解决这个问题我只是不知道该怎么做。

三种情况下的答案都是相似的。您将尝试奇数 (x=2i+1)、平方 (i^2) 或幂 (2^i) 的候选，而不是通过二分法尝试整数候选 x=i。在这三种情况下，都有k个不同的值可以尝试，最坏的情况下需要Lg(k)个比较。

唯一的区别是当您用 n:

表示这些数字时

Lg(k) = Lg(n/2) = Lg(n)-1
Lg(k) = Lg(√n) = Lg(n)/2
Lg(k) = Lg(Lg(n))

如果你能找到组你要进行二分查找的数，你只需要取的对数count of numbers numbers in your new set. 那是因为你定位了你的目标数字后，你只需要对它们进行二分查找就可以找到 x.

总共给定了 n 个数字来执行二进制搜索，它们是 集合 {1, ..., n}。

当x为奇数且n可表示为2^k

因为 x 是奇数，所以你只能在集合的奇数中找到它。因此，与 n 相反，你有 n/2 大小的设置来找到你的目标号码。作为 n = 2^k，你的新集合的大小（我们称它为n' ), 即 = n/2。对这组数字进行二进制搜索的最坏情况运行time 将是 Log(numbers in n') 即 Log (n/2) 或

(Log n) - 1 = k - 1

当x为正方形且n可表示为(2^k)²

在这种情况下，您的新目标数字集将减少为仅包含完全平方数。这个新集合将包含数字 {1, 4, 9, ..., n}。这组数字的个数等于√n。想一想，当它只有1时，个数是√1 = 1。当它有1和4时，里面的数个数是√4 = 2。

因此，根据你的新集合的大小 n' = √n，最坏情况运行次对这组新数字的二分查找又是 = Log(numbers in n') = Log(√n) 等于

(Log n) / 2 = k

当x为2的幂且n可表示为2^{( 2^k)}

在这里，您的目标设置为运行二进制搜索减少到仅那些 2 的幂数。简单明了，该集合将包含像 {1, 2, 4, 8...n}。此集合中的数字计数等于 (Log n) + 1。同样，您可以看到当集合只有 1 时，计数为 (Log 1 (= 0) + 1) = 1。当集合有 1 和 2 时，计数为 (Log 2 (= 1) + 1) = 2等等。

这个运行时间复杂度又是Log(n'中的数字)=Log((Log n)+1)。如果你容忍日志中的1，它是

Log(Log(n)) = k

修改二进制搜索以获得更好的性能

Modifying Binary Search to obtain better performances

algorithm

binary-search

当x为奇数且n可表示为2^k

当x为正方形且n可表示为(2^k)²

当x为2的幂且n可表示为2^{( 2^k)}

修改二进制搜索以获得更好的性能

Modifying Binary Search to obtain better performances

algorithm

binary-search

当x为奇数且n可表示为2k

当x为正方形且n可表示为(2k )2

当x为2的幂且n可表示为2( 2k)

当x为奇数且n可表示为2^k

当x为正方形且n可表示为(2^k)²

当x为2的幂且n可表示为2^{( 2^k)}