尝试的解决方案: (1) 假设 x 是奇数。我们已将搜索集减少了一半。最坏情况下的复杂度现在为 log(n/2) = logn - 1。现在我们只需对奇数执行二分查找即可。
我不确定这个解决方案是否正确，因为我不知道解决此类问题的一般方法。我希望能找到所有三个部分的解决方案。如果我没有迷失的话，我肯定会尝试更多的问题。在发布之前我已经尝试提前解决这个问题，但我只是不知道该怎么做。
最佳答案
如果您可以找到必须执行二分搜索的数字集合，则只需记录新集合中的数字计数.这是因为当你本地化了你的目标数字后，你只需要对它们进行二分查找就可以找到x。
给定总共 n 个数字来执行二分搜索，它们是集合 {1, ..., n}。
当x为奇数且n可表示为2k
由于 x 是奇数，因此您只能在集合的奇数中找到它。因此，与 n 不同，您有 n/2 大小的集合来查找目标数字。如 n = 2k，新集合的大小(我们称之为n')= n/2。对这组数字进行二分搜索的最坏情况运行时间将是 Log(n' 中的数字)，即 Log (n/2) 或
(Log n) - 1 = k - 1
当x为完全平方数且n可表示为(2k)2
在这种情况下，您的新目标数字集将减少为仅包含完全平方数。这个新集合将包含数字 {1, 4, 9, ..., n}。该集合中的数字数量等于√n。想一想，当它只有 1 时，数量是 √1 = 1。当它有 1 和 4 时，它的数量是 √4 = 2。
因此，根据新集合的大小 n' = √n，在这组新数字上进行二分搜索的最坏情况运行时间再次 = Log (n' 中的数字)= Log(√n) 等于
(Log n) / 2 = k
当x为2的幂且n可表示为2(2k)
在这里，要运行二分搜索的目标集被简化为仅包含 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
关于algorithm - 修改二分搜索以获得更好的性能，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/32829752/