arrays - 对数基3次搜索算法

Question

完全公开这是一个家庭作业问题，因此，我不会要求具体的解决方案，只是对一些问题的一般答案。问题正文如下:

Given a sorted array of type T that must implement the Comparable interface, write a Java generic method that finds a specific element in the array and returns it, or returns null if it is not found. Note that your algorithm must run worse-case in log base 3 time, a log base 2 (binary search) solution will receive no credit

还有一个额外的规定，算法必须是迭代的，而不是递归的。

1) 所以我的第一个问题是，如何确定算法以对数为底 3 而不是对数为底 2 运行？两者仅相差一个常数因子，所以即使我分析了算法的结构，我怎么知道我是在 Log3(n) 时间内运行，还是仅在 (~0.63)(Log2(n)) 内运行时间？这有关系吗？

2) 我的印象是二分搜索或多或少是搜索排序数组的标准快速算法，所以除了二分搜索和线性搜索之外，还有哪些其他搜索算法可以让我在这方面寻求灵感？

3) 是否有我遗漏的东西，一些允许比标准二进制搜索更快地搜索数组的规定？

非常感谢任何帮助，如果这个问题相当具体，我很抱歉，但我认为它的某些部分可以普遍适用。

Answer 1

1. 是的，O(log(n)) 不关心 log 是以 2 为底还是以 3 为底。

2. 假设现在的任务是使用不超过一定数量的比较。我们可以证明，在最坏的情况下，在没有常数因子的情况下，通过不超过 log₃(N) 次比较来解决它是不可能的。对于新手来说，如果数组有三个元素，只比较一次是不可能找到元素或者报错的。同样，对于一个九元数组，两次比较显然是不够的。可以使用鸽巢原理和一些注意来证明大 N 也是不可能的，尽管我承认我没能在几分钟内做出简短证明。
   我尝试对大 N 进行证明的想法是这样的(尽管细节变得乏味)。如果所有的数组元素都不同并且也不同于我们搜索的 X，那么在询问 K 个问题后我们只能得到 K 位的信息，因此最多可以区分数组的 2^K 段X 可能在哪里。然后，存在一段一定长度(比如3个元素)，其中有一个我们没有比较过但仍然可以等于X的元素。将其变为X，我们得到一个反例数组。