It is possible to change the way that we pick the dividing point in a binary search, and still get a working search routine. However, where we pick the dividing point could affect the performance of the algorithm.
(a) If we change the dividing point computation in function binary from i = (l + r)/2 to i = (l + ((r − l)/3)), what will the worst-case running time be in asymptotic terms? If the difference is only a constant time factor, how much slower or faster will the modified program be compared to the original version of binary?
(b) If we change the dividing point computation in function binary from i = (l + r)/2 to i = r − 2, what will the worst-case running time be in asymptotic terms? If the difference is only a constant time factor, how much slower or faster will the modified program be compared to the original version of binary?
Already registered? Login
Not Account? Sign up
Enter your email address to reset your password
Back to Login? Click here