Difference between revisions of "TADM2E 4.33"

From Algorithm Wiki
Jump to: navigation, search
(Recovering wiki)
 
(Recovering wiki)
 
Line 1: Line 1:
 
Apply binary search to find out transition point
 
Apply binary search to find out transition point
<pre>
+
<pre>
 
Assume set indexes are zero based
 
Assume set indexes are zero based
 
FindIndex(A):
 
FindIndex(A):
 
     1. low =  0, high =1
 
     1. low =  0, high =1
 
     2. mid = (low + high)/2
 
     2. mid = (low + high)/2
     3. if(A[mid] &gt; mid) then
+
     3. if(A[mid] > mid) then
 
             Index will lie in left half of the array
 
             Index will lie in left half of the array
 
                 high = mid-1
 
                 high = mid-1
 
                 Go to step 2.
 
                 Go to step 2.
         else if (A[mid] &lt; mid) then
+
         else if (A[mid] < mid) then
 
             Index will lie in right half of array
 
             Index will lie in right half of array
 
             low = mid + 1
 
             low = mid + 1
 
         else
 
         else
 
             return mid
 
             return mid
&lt;/pre&gt;
+
</pre>
 
--[[User:Max|Max]] 07:31, 25 June 2010 (EDT)
 
--[[User:Max|Max]] 07:31, 25 June 2010 (EDT)

Latest revision as of 18:23, 11 September 2014

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)