Finding Maximum and Minimum Elements
You'll learn how to traverse arrays to locate the largest and smallest values, plus a clever trick to find both with fewer comparisons.
The Core Idea
Imagine you're judging a contest and need to identify both the winner (highest score) and the participant who needs the most encouragement (lowest score). You'd walk through the list once, keeping track of the best and worst you've seen so far. Finding max and min in arrays works exactly the same way.
Finding Maximum or Minimum Separately
The straightforward approach: assume the first element is your current "champion," then check each remaining element. If you find a larger value when searching for max (or smaller for min), crown a new champion.
scores = [45, 92, 67, 23, 88]
# Find maximum
max_score = scores[0]
for score in scores:
if score > max_score:
max_score = score
# max_score is now 92
This requires n−1 comparisons for an array of length n.
Finding Both with Minimal Comparisons
Here's the clever optimization: compare elements in pairs first. The larger goes to the "max candidate pool," the smaller to the "min candidate pool." Then find the max among candidates and min among candidates separately.
This technique uses roughly 3n/2 comparisons instead of 2n (if you found max and min separately), saving about 25% of comparisons—valuable when working with massive datasets.
Practical Notes
- Always initialize with the first element or appropriate sentinel value
- Watch out for empty arrays (they have no max/min)
- These operations require visiting every element: O(n) time complexity
Key Takeaway: Finding max or min requires scanning the entire array with a running champion; finding both simultaneously can be optimized by comparing elements in pairs first, reducing total comparisons by about 25%.