In class, I learned an implementation of binary search that used up to two comparisons for each
Question:
In class, I learned an implementation of binary search that used up to two comparisons for each recursive call, checking for both xa[mid]. A better approach that uses only one comparison for each recursive call is the following: (a) first, check to see which half of the array x may lie in: either from low to mid or from mid+1 to high. Then make a recursive call on that half of the array (b) only when we are down to a base case of an array subsection of length 1 to we finally perform an equality check on x. If x is equal to the single value in this subsection we return its index; otherwise, we return -1. What this approach does is whittle down the size of the array section until we get to the only the possible location that x could be and then we check (in the base case) whether or not x is actually there. How would I write a version of binary search that uses this approach?
International Marketing And Export Management
ISBN: 9781292016924
8th Edition
Authors: Gerald Albaum , Alexander Josiassen , Edwin Duerr