在无限长度排序数组中查找元素

Question

给定具有正整数和负整数的无限长度排序数组.在其中找到一个元素.

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

有两种方法:

方法1:

将索引设置在位置100,如果要找到的元素较少,则在前100个项目中进行二进制搜索,否则将下一个索引设置在位置200处.这样,继续将索引增加100,直到项目更大.

设置索引的幂2.首先将索引设置在位置2,然后是4,然后是8,然后是16,依此类推.再次从位置2 ^ K到2 ^(K + 1)进行二元搜索,其中项目位于其间.

在最佳情况和最差情况下,这两种方法中的哪一种会更好？

Answer 1

第一种方法在元素的索引中是线性的(O(k)其中k是元素的索引).实际上,您将需要k/100迭代来查找大于搜索元素的元素,即O(k).

第二种方法将在同一索引中进行对数.O(logk).(k元素的索引在哪里).在这里,您将需要log(k)迭代,直到找到更高的元素.然后二进制搜索2^(i-1),2^i(i迭代编号在哪里),也将是对数,总计O(logk)

因此,第二个更有效.

@czchlong：只有在最后一次迭代之后才需要进行二分查找，在那之前搜索一个值是没有意义的，因为它不会在这个范围内。第一次 i-1 迭代只是检查是否 `x < arr[2^i]`，如果是 - 前进到下一次迭代，没有任何二分搜索。 (2认同)