在无限长排序数组中查找元素
给定一个无限长的排序数组，该数组同时具有正整数和负整数。在其中找到一个元素。
数组中的所有元素都是唯一的，数组在正确的方向上是无限的。
有两种方法：
方法1：
将索引设置在位置100，如果要查找的元素较少，则在前100个项目中进行二进制搜索，否则将下一个索引设置在位置200。以这种方式，继续将索引增加100，直到该项目更大为止。
方法二：
将索引设置为2的幂。首先将索引设置在位置2，然后是4，然后是8，然后是16，依此类推。再次从位置2 ^ K到2 ^（K +
1）进行二进制搜索，其中项目位于两者之间。
在最佳情况和最坏情况下，两种方法中哪一种会更好？
回答：
第一种方法在元素的索引（O(k)其中元素k的索引为）中将是线性的。实际上，您将需要k/100迭代才能找到比搜索到的元素更大的元素O(k)。
第二种方法将在同一索引中是对数的。O(logk)。（k元素的索引在哪里）。在这里，您将需要log(k)迭代，直到找到更高的元素。然后之间的二进制搜索2^(i-1)，2^i（其中i是迭代次数），将是对数，以及，在共计O(logk)
因此， 。
以上是 在无限长排序数组中查找元素 的全部内容， 来源链接： utcz.com/qa/409343.html
