在无限长的排序数组中查找元素 [英] 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位置，如果要查找的元素较少，则在前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) 进行二分搜索，其中 item 介于两者之间.

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) where k是元素的索引).实际上，您将需要 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 than the searched element, which is O(k).

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

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屋！