查找在无限长排序的数组中的元素 [英] Find an element in an infinite length sorted array

问题描述

由于同时具有正，负整数的无限长排序的数组。查找中的一个元素。

Given an infinite length sorted array having both positive and negative integers. Find an element in it.

修改
阵列中所有的元素都是唯一的，并且阵列中的无限在正确的方向。

EDIT
All the elements in the array are unique and the array in infinite in right direction.

有两种方法：

在位置100设置的索引，如果被发现的元素是在previous 100项，否则设定在位置200中的下一个索引以这种方式以下，二进制搜索，继续由100增大索引直到该项目是更大的。

Set the index at position 100, if the element to be found is less, binary search in the previous 100 items, else set the next index at position 200. In this way, keep on increasing the index by 100 until the item is greater.

集2.首先设置索引位置2处，然后4，则如图8所示，然后16等的索引中的功率。再次执行从位置二进制搜索2 ^ K至2 ^（K + 1），其中产品之间。

Set the index in power of 2. First set the index at position 2, then 4, then 8, then 16 and so on. Again do the binary search from position 2^K to 2^(K + 1) where item is in between.

这两种方法的会更好无论是在最好的情况和最坏的情况？

Which of the two approaches will be better both in best case and worst case?

推荐答案

第一种方法将是线性的元素的索引（ O（K），其中氏/ code>是元素的索引）。其实，你将需要 K / 100 迭代发现这是大于搜索到的元素，它是 O（K）。

The first approach will be linear in the index of the element (O(k) where k is the index of the element). Actually, you are going to need k/100 iterations to find the element which is greater then the searched element, which is O(k).

第二种方法将是对数相同的索引。 O（稳定常数）。 （其中， K 是元素的索引）。在这里，你会直到找到​​更高的元素需要日志（K）迭代。在 2 ^（I-1）， 2 ^ I （其中然后二进制搜索我为迭代次数），将是对数为好，共在 O（稳定常数）

The second approach will be logarithmic in the same index. O(logk). (where k is the index of the element). In here, you are going to need log(k) iterations until you find the higher element. Then binary search between 2^(i-1), 2^i (where i is the iteration number), will be logarithmic as well, totaling in O(logk)

因此​​，二是更有效

这篇关于查找在无限长排序的数组中的元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！