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?
To analyze the worst-case running time and the difference in performance for the modified versions of the binary search algorithm, we need to consider how the dividing point affects the number of iterations required to find the target element.
(a) If we change the dividing point computation in function binary from i = (l + r)/2 to i = (l + ((r - l)/3)), the worst-case running time will still be O(log n), where n is the size of the input array. This is because we are still effectively dividing the search space in half at each step.
However, the modified program will be slightly slower compared to the original version of binary. In the original binary search, the dividing point is computed as the average of the left and right indices, which can be done in constant time. In the modified version, we compute the dividing point as the sum of the left index and one-third of the difference between the right and left indices. This requires an extra arithmetic operation, involving subtraction, division, and addition, which takes a bit longer than a simple average calculation.
(b) If we change the dividing point computation in function binary from i = (l + r)/2 to i = r - 2, the worst-case running time will still be O(log n). This is because we are still dividing the search space in half, albeit by using a fixed offset of 2 from the right index.
The modified program will not significantly affect the overall performance compared to the original version of binary. Although the calculation of the dividing point becomes a constant offset from the right index, this offset is independent of the size of the input array. Therefore, the difference in running time will be a constant time factor, meaning the modified program will perform slightly faster or slower by a constant factor but not affect the asymptotic complexity of the algorithm.
In summary, both modifications to the dividing point computation will not change the worst-case running time of binary search, which remains O(log n). However, the modified programs might have slightly different performance due to the additional arithmetic operations introduced in the modified computation of the dividing point.