Everyone knows how to find the biggest number in a list: scan it once, keep the largest you’ve seen. Want the smallest too? Scan again — or track both at once, checking each element against both running values as you go. Either way that’s roughly two comparisons per element. Divide and conquer gets both extremes for noticeably less: split the array, solve each half for its own (min, max) pair, then merge the two pairs with exactly two comparisons, regardless of how large the halves were. Step through it below and watch the comparison count come in under the naive total every time.

Leave a Reply