We know we can do binary search on a sorted array A[1::n] in (log n) time. But w

Question

We know we can do binary search on a sorted array A[1::n] in (log n) time. But what if
we don’t know the value n?
Your task in this problem is to give (log n)-time algorithm to search such an array for a
target key K, returning the index in A of K, if it exists, or else -1. (You can assume for
simplicity that the values of A are all distinct.)

2. We know we can do binary search on a sorted array A[1.n] in e(log n) time. But what if we don't know the value n? Your task in this problem is to give e(log n)-time algorithm to search such an array for a target key K, returning the index in A of K, if it exists, or else -1. (You can assume for simplicity that the values of A are all distinct.) Since you don't know A's length, a common occurrence will be "falling of the end" of A, ie., trying to access Ali] for an i greater than (the unknown value of) n. In programming doing this might return an error or throw an exception. For the purposes of this problem, it may be simpler to assume that A[i] will evaluate to "oo" when i > n, i.e., a comparison between An +1] and other actual key (either the target K or any Alk] for 1 3 k 3 n will always say Ain +1] is larger.

Explanation / Answer

Since array is sorted, the first thing clicks into mind is binary search, but the problem here is that we don’t know size of array.
If the array is infinite, that means we don’t have proper bounds to apply binary search. So in order to find position of key, first we find bounds and then apply binary search algorithm.

Let low be pointing to 1st element and high pointing to 2nd element of array, Now compare key with high index element,
->if it is greater than high index element then copy high index in low index and double the high index.
->if it is smaller, then apply binary search on high and low indices found.

Please find the pseudocode below.

PSEUDOCODE

=========================

// Simple binary search algorithm

Function binarySearch(arr as array, low, high, k)

{

if (high >= low)

{

mid = low + (high - low)/2;

if (arr[mid] == k)

return mid;

if (arr[mid] > k)

return binarySearch(arr, low, mid-1, k);

return binarySearch(arr, mid+1, high, k);

}

// function takes an infinite size array and a key to be

// searched and returns its position if found else -1.

// We don't know size of arr[] and we can assume size to be

// infinite in this function.

// NOTE THAT THIS FUNCTION ASSUMES arr[] TO BE OF INFINITE SIZE

// THEREFORE, THERE IS NO INDEX OUT OF BOUND CHECKING

Function findPos(arr as array, k as key)

{

low = 0, high = 1;

val = arr[0];

// Find high to do binary search

while (val < key)

{

low = high; // store previous high

high = 2 * high; // double high index

val = arr[high]; // update new val

}

// at this point we have updated low and

// high indices, Thus use binary search

// between them

return binarySearch(arr, l, h, key);

}

Time Complexity: Let p be the position of element to be searched. Number of steps for finding high index ‘high’ is O(Log p). The value of ‘high’ must be less than 2*p. The number of elements between high/2 and high must be O(p). Therefore, time complexity of Binary Search step is also O(Log p) and overall time complexity is 2*O(Log p) which is O(Log p).

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.