3 Sorted arrays: Searching faster, at a price
In chapter 2, we introduced static arrays, and you learned how to use them as containers to hold elements without worrying about the element’s order. In this chapter, we take the next step: keeping the array elements sorted. There are good reasons for ordering arrays, such as domain requirements or to make some operations on the array faster. Let’s discuss an example that shows the tradeoffs and where we can get an advantage by keeping the element of an array in order.
What’s the point of sorted arrays?
In the previous chapter, we looked at arrays as containers where the order of their entries doesn’t matter. But what if it does? Well, when the order does matter, it changes everything, including how we perform the basic operations we have implemented.
Before we look at how, let’s try to understand when a sorted array can be useful.
The challenge of the search ninja
Our little friend Mario got excited about both coding and baseball cards. He started saving his lunch money to buy cards to play with his friends. He bought so many cards that it became difficult to carry and find them. His father bought him a binder to make them easier to carry around, but with hundreds of cards, even with the binder, it was still hard to find the ones he needed.