5.5

Apply binary search to find out transition point

Assume set indexes are zero based
FindIndex(A):
    1. low =  0, high =1
    2. mid = (low + high)/2
    3. if(A[mid] > mid) then
            Index will lie in left half of the array
                high = mid-1
                Go to step 2.
        else if (A[mid] < mid) then
            Index will lie in right half of array
            low = mid + 1
        else
            return mid

-- Max 07:31, 25 June 2010 (EDT)

Back to Chapter 5