Difference between revisions of "TADM2E 4.33"
From Algorithm Wiki
(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> | |
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] | + | 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] | + | 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 | ||
| − | + | </pre> | |
--[[User:Max|Max]] 07:31, 25 June 2010 (EDT) | --[[User:Max|Max]] 07:31, 25 June 2010 (EDT) | ||
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)
