TADM2E 4.33

From Algorithm Wiki
Revision as of 18:13, 11 September 2014 by Algowikiadmin (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Apply binary search to find out transition point <pre> 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

</pre> --Max 07:31, 25 June 2010 (EDT)