Today's brief lesson will cover one of the efficient algorithms enabled by sorting: binary search! This is a fun example of an algorithm that you can approach either recursively or iteratively. We'll walk through it visually and then let you tackle it on today's homework problem.
One of the reasons that sorting is such an important algorithmic primitive is that it enables other efficiency algorithms. For example, we've already seen linear array search, which has runtime O(n):
Given that O(n) represents searching the entire array, it is clearly the worst case runtime for array search. But, it is also the best case if we have no idea where the item could be!
But what if we knew something about the structure of the data in the array. Specifically, what if we knew that it was sorted? Could we do better?
Or, as my old graduate school friend David Malan famously explained it:
Binary search is one recursive algorithm where the O(log n) nature of the algorithm is fairly easy to understand. Start with an array of N items. After one round, you have N / 2 left to consider. Then N / 4. Then N / 8. Until you either get to 1, or you find the item somewhere along the way. So in the worst case we do O(log n) steps, and in the best case we may do better. Cool!
As promised, a few cool search visualizations culled from the amazing interwebs. This one has sound!
These are also pretty good, as they show runtime for different inputs as well.
Now it's your chance to implement this classic algorithm! There are good approaches that use both recursion and iteration. The iterative approach maintains the start and end index of where the item might be in the array and adjusts these on each iteration. The recursive approach has the base case being an empty or single-item array, and makes the problem smaller by determining whether the item should be in the left half-array or right half-array. Good luck and have fun!