The Sorted Array

This chapter builds binary search over a sorted array, implemented first iteratively and then recursively, and derives its ${\log }_{2}n$ step count against linear search’s $n$. It then builds a SortedArray that maintains a sorted-order invariant, implementing add, search, and remove with binary search.

After reading this chapter, you should be able to:

• Explain why keeping data in sorted order lets you search much faster, by repeated halving, than the linear scan an unsorted collection needs
• Implement and trace binary search over a sorted array, returning an index (or -1), and refine it to report the insertion point where a missing value belongs
• Write a search recursively with a base case and a recursive case, and explain why moving toward the base case makes it terminate
• Hide a recursion’s index/bounds parameters behind a public method that delegates to a private overloaded helper (information hiding)
• Derive that binary search takes about ${\log }_{2}n$ steps, and compare how linear ($n$) and binary ($\log n$) search scale as the input grows
• Build a SortedArray that maintains a sorted-order invariant, implementing add, search, and remove with binary search and explaining why the invariant determines which operations the contract can offer

You can download the accompanying code for this chapter: starter and solution.

Sections

1. Why Keep It Sorted?
2. Binary Search
3. Binary Search, Recursively
4. Searching Half the Array
5. Passing the Bounds
6. The Base Case
7. The Base Case and the Recursive Case
8. Recursive Linear Search
9. A Public Method and a Private Helper
10. A Helper for Binary Search
11. Recursive vs. Iterative
12. Counting the Steps in Binary Search
13. Linear vs. Binary Search, Side by Side
14. The SortedArray
15. Adding in Order
16. Searching with Binary Search
17. Removing
18. Should we offer a set operation?