performance - 在无限长的排序数组中查找一个元素

Question

给定一个包含正整数和负整数的无限长排序数组。在其中找到一个元素。

编辑
数组中的所有元素都是唯一的，并且数组在正确的方向上是无限的。

有两种方法:

方法一:

在100位置设置索引，如果要查找的元素少，则在前100项中进行二分查找，否则在200位置设置下一个索引。这样，不断增加索引100，直到找到该元素更大。

方法 2:

设置索引的2次方。先设置索引在2的位置，然后是4，然后是8，然后是16，依此类推。再次从位置 2^K 到 2^(K + 1) 进行二进制搜索，其中 item 位于两者之间。

在最好的情况和最坏的情况下，这两种方法中哪一种更好？

Answer 1

第一种方法在元素的索引中是线性的(O(k)，其中 k 是元素的索引)。实际上，您将需要 k/100 次迭代才能找到大于搜索元素的元素，即 O(k)。

第二种方法将在同一索引中取对数。 O(logk)。 (其中 k 是元素的索引)。在这里，您将需要 log(k) 迭代，直到找到更高的元素。然后在2^(i-1)、2^i(其中i是迭代次数)之间进行二分查找，也将是对数的，总计 O(logk)

因此，第二种效率更高。