Problem
Given a set S that is sorted and contains discrete integers, (no element appears twice), and that is infinitely large in the positive direction, design an algorithm that can determine if a given integer x is in the list in O(lgn)-time. Note: You know the value of the maximum element, m. The list contains a finite amount of discrete elements after which the maximum element is repeated infinitely.
Solution
Since the list is sorted and contains discrete elements, the first step is to find the location of where the maximum element occurs. Note that finding the maximum requires at least O(n)-time.
Algorithm find_x( S, m, x )
Input:
S, an infinite sorted list of discrete integers
m, the value of the maximum element in the list
x, the element to search for
Output: True if x is in S, false otherwise
begin
i = 0;
while( S[i] != m ) {
i = 2i;
}
return binary_search( S, x, 0, i );
end
Essentially, we search for the position of the maximum element to establish an upper-bound to the list so it can be passed off to binary search, which accepts the list, element to search for, lower and upper searching bounds to do the rest of the work.
Note that by doubling the index on each iteration, finding the maximum takes O(lgn)-time rather than O(n) time. This enables the algorithm to run in O(lgn)-time overall, rather than being bounded by the O(n) time it takes to find the position of the maximum element.
\( \therefore T(n) = O(lgn) \)