完全公开这是一个家庭作业问题,因此,我不会要求具体的解决方案,只是对一些问题的一般答案。问题正文如下:
还有一个额外的规定,算法必须是迭代的,而不是递归的。
1)所以我的第一个问题是,我如何确定算法以对数为基数 3 而不是以对数为基数 2 运行?两者仅相差一个常数因子,因此即使我分析了算法的结构,我怎么知道我是在 Log3(n) 时间内运行,还是仅在 (~0.63)(Log2(n)) 中运行时间?它甚至重要吗?
2)我的印象是二分搜索或多或少是搜索排序数组的标准快速算法,因此除了二分搜索和线性搜索之外,还有哪些其他搜索算法可以从中寻找灵感?
3)有什么我遗漏的,一些规定可以比标准的二进制搜索更快地搜索数组吗?
非常感谢任何帮助,如果这个问题相当具体,对不起,但我认为它的某些部分可以普遍适用。
最佳答案
我为大 N 尝试的证明想法是这样的(尽管细节变得乏味)。如果所有数组元素都是不同的,并且也不同于我们搜索的 X,那么在问 K 个问题后我们只能得到 K 位信息,因此可以区分不超过 2K 的数组段,其中 X 可能是。然后,存在一定长度的段(比如3个元素),其中有一个我们没有比较但仍然可以等于X的元素,将其改为X,我们得到一个反例数组。
关于arrays - 对数基3次搜索算法,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/39571091/