Grokking Data Structures

3 Sorted arrays: Searching faster, at a price

In this chapter

• why keep an array sorted
• adjusting the insert and delete methods for sorted arrays
• the difference between linear search and binary search

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 ...