Finding Minimum and Maximum Efficiently
You'll learn how to find both the minimum and maximum values in an array using fewer comparisons than scanning twice.
The Naive Approach
When you need to find both the smallest and largest values in an array, the obvious solution is to scan through the array twice: once to find the minimum (n-1 comparisons) and once to find the maximum (n-1 comparisons). That's 2n-2 comparisons total.
But we can do better!
The Paired Comparison Strategy
Instead of treating min and max as separate problems, we can process elements in pairs:
- Compare two elements against each other first (1 comparison)
- Compare the smaller one against the current min (1 comparison)
- Compare the larger one against the current max (1 comparison)
This gives us 3 comparisons per pair of elements.
The Math
For an array of n elements, we process n/2 pairs, using 3 comparisons per pair:
- Total comparisons: 3n/2 (compared to 2n with two scans)
- That's a 25% reduction in comparisons!
The Intuition
Think of it like organizing books by height. Instead of finding the shortest book in one pass and then the tallest in another, you grab two books at a time. Compare them to each other first, then only compare the shorter one to your "shortest so far" and the taller one to your "tallest so far." You've saved one comparison per pair!
Key Takeaway: By processing elements in pairs and comparing each pair against each other before comparing to the running min/max, you can find both the minimum and maximum using only 3n/2 comparisons instead of 2n.