Binary search on unknown size array

Question

Suppose an array has been given and want to find element in that array , how can you search an element in that array using binary search and that given array is already sorted and size of the array is unknown. Linear search can be applied but I am trying to figure out for faster search than linear algorithm.

Answer 1

If you can test whether you have fallen out of the array range, then you could use a modified binary search (assume 1-based array):

1. lower = 1, upper = 1;
2. while (A[upper] < element) upper *= 2;
3. Normal binary search on (lower, upper).

Otherwise, there is no real way to do it: assume you find something somewhere that equals to the element you need, you cannot know if it already falls out of the array.

Answer 2

Assuming the array A is sorted (otherwise you can't do binary search), and the element you're searching for is k, you can find an index i such that k < A[i], and then do binary search from 1 to i (1-indexed array). This is because once k < A[i], k is guaranteed to be found (or not found) in the range of sorted elements A[1..i].

To find the index i, you would start at i = 1, then double it if k > A[i]. This is like binary search except you're doubling the search range, so it will still have a O(log n) running time.

The algorithm is something like: Set i = 1, then repeat until k <= A[i]:

• if k > A[i] then let i = i*2

If k == A[i], then you're done, otherwise do binary search as usual on A[1..i].