The binarySearch algorithm of Section 5.2.2 first checks whether the target is equal to the current middle entry, before proceeding to the left or right halves if required. There is another variant of binary search which postpones the equality check until the very end. This version is presented belowwe call it lazy binary search:

(a) Trace this algorithm on the example array of Section 5.2.2 with 19 as the target. How many comparisons does it make?

(b) Trace the algorithm on this array with 26 as the target. What is the number of comparisons made?

(c) How many comparisons does this algorithm makes in general for an array of size n? Give an exact figure, not big O.

(d) Under what conditions is it preferable to use this version instead of the original binary search version?