(Finding similar pizzas) You are given a stack of n pizza boxes of the same size, each containing 1 pizza. The pizzas in the boxes are sorted by increasing diameter; the diameters are all at most 40cm.

Hint: What happens if they all dier by more than that? Give an algorithm for nding such a pair. The only way your algorithm may learn the diameter of a pizza is by opening its box and measuring it. Well call that operation measure(i), where i is the number of the box being opened. Your algorithm should open as few pizza boxes as possible. For full credit, it should open O(log n) boxes in the worst case.

[Hint: Remember that the boxes are sorted by pizza size. Think binary search. If you look at the middle pizza box, what can you conclude? You might need to handle odd and even boxes separately.] In your solution, as with all algorithmic problem this semester, you must Briey describe how your algorithm works in English. 1

Give pseudocode for your algorithm.

Prove that your algorithm is correct.

Analyze the worst-case complexity of your algorithm as measured by the number of opened boxes.