# 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)