# 30.5 Exercises

- 1.Suppose we have a sorted array in Java. What is the best approach for finding a particular item in the array: binary search or linear iteration?
- 2.Repeat the above exercise for a sorted array stored on physical tape.
- 3.Given the array
`[90, 50, 20, 30, 40, 10, 60, 50, 30]`

, what would be the best pivot?

On a physical tape, the runtime of the algorithm will be dominated by the time to accelerate the physical piece of tape. In the worst case, binary search would involve scanning to the middle of the tape, then a quarter of the way back, then an 1/8th of the way forward, and so forth. In the worst case, we have to cover N/2 + N/4 + N/8 + ... + 1 or O(N) spaces on the tape. However, all that acceleration back and forth will result in an algorithm that is almost certainly slower in the worst case than just scanning forwards.

- 1.If we have 10 items to sort, how many compares will it take to selection sort all of the items?
- 2.What is the depth of the quicksort recursive tree in the best and worst case? Give an exact answer, not a theta bound.

- 1.Assume that we always pick the leftmost item as our pivot for quicksort. Identify the three types of arrays that will cause a worst-case runtime. For partitioning, assume that we partition into two arrays: items less than or equal to the pivot, and items greater than the pivot.

The two types of arrays are:

- 1.Arrays already in sorted order. There will always be nothing to the left of the pivot, since the pivot will always be the smallest item.
- 2.Arrays in reverse-sorted order. This has the same problem as (1), except that the pivot will always be the largest item.
- 3.Arrays where all items are equal. Everything will be partitioned into the left (less than or equal to array), and nothing in the greater-than array.

Last modified 10mo ago