Why Keep It Sorted?

You are reading this coursebook online, so you have a search box. Type in a word and you immediately get every page that contains it. I grew up with physical textbooks, and what we had instead was the index: a list of words at the back of the book, each with the page numbers where it appeared. Not every word, only the ones the author thought worth indexing: important terms, key topics, technical jargon.

The index was not in the order the words appeared in the book. It was sorted alphabetically. That is what let you find a word quickly: you could jump to roughly the right place instead of reading every entry, one by one, until you reached the one you wanted. For example, assume you were looking for “Selection Sort”, and assume the index was seven pages long. You could jump to the middle and see which letter groups are there. You could then decide if “S” appears in the pages before or after, and repeat the process to find “Selection Sort”. Once you find it, you look at what page number(s) it lists, then go to those pages to read about selection sort.

Phone books worked the same way, sorted by last name, and they are the closer match to what we are about to build. A phone book is not an index into something else. It is the list itself, and it is sorted, so you can find a name in it fast. The strategy would be the same: do not read every name front to back. Instead, open in the middle, figure out which half does not contain the name you are looking for, and repeat the process for the other half, until you find the name (or are convinced it is not in the phone book).

Now recall how we search a DynamicArray. Its contains scans from front to back, one element at a time, because the elements are stored in whatever order they were added. Seeing that arr[0] is not the target tells you nothing at all about arr[1], so you have to keep going. In the worst case you check every element. And we cannot avoid this, because DynamicArray.add appends each new element to the end, in arrival order. The array is never sorted, so there is no order for a faster search to use.

Once the elements are in sorted order, a comparison tells you much more. Look at the middle element. If it is smaller than the target, then everything to its left is smaller than it, so everything to its left is smaller than the target too, and the target cannot be there. If it is larger than the target, the same reasoning rules out everything to its right. Either way, one comparison rules out half the elements. Repeat on the half that is left, and you keep halving until you find the target or run out of elements. This is called binary search.

In the next few sections we will implement binary search, count how many steps it takes, and compare it to linear search. Then we will build a data structure that maintains sorted order, so binary search always applies to it.