time-complexity - 在排序数组中进行搜索所需要的紧迫的较低时间复杂度是多少

Question

例如，在排序时，严格的下限是N * log（N），其中N是数组的大小

如何在排序数组中搜索？我认为这是对数（N），但我不确定100％。

一切也都基于比较，除了输入数组本身，不能使用任何其他外部存储器

提前致谢

Answer 1

搜索简单排序数组的最佳解决方案是二进制搜索，其时间复杂度为O（log 2（N））。最坏的情况发生在搜索的元素不在数组中时，并且恰好进行“ log 2（N）+ 1”次迭代。请参见Binary Search Performance。

我相信您只能在提及复杂性的上限和下限时谈论“紧密性”。下界（大Omega）通常更难计算，通常不如上限（大O）有用。紧密边界（大Theta）同时考虑了上限和下限。

从技术上讲，下限是Ω（1），因为您可以在第一个比较中找到要搜索的元素。有关二进制搜索的时间复杂度的进一步讨论，请参见Is binary search theta log (n) or big O log(n)。