Review & Cheat Sheet

Key Takeaways

• Sorting is a pre-processing investment that often makes repeated queries cheap.
• Binary search is a boundary-finding framework, not just “find exact value”.
• Stable vs unstable sort matters for multi-key workflows.
• Real systems care about constants, cache behavior, and partially sorted inputs.

Approach Matrix

Task	Common Choice	Why
Small nearly-sorted arrays	Insertion sort	low overhead, adaptive
General in-memory sort	Quick/Merge/TimSort	practical balance
Guaranteed worst-case bound	Merge/Heap sort	predictable performance
Ranked queries after sort	Binary search variants	O(log n) boundaries

Binary Search Boundary Pattern

Find first index where predicate becomes true.

Java

int firstTrue(int[] a) {
  int l = 0, r = a.length; // [l, r)
  while (l < r) {
    int m = l + (r - l) / 2;
    if (predicate(a[m])) r = m;
    else l = m + 1;
  }
  return l;
}

Go

func FirstTrue(a []int, predicate func(int) bool) int {
	l, r := 0, len(a)
	for l < r {
		m := l + (r-l)/2
		if predicate(a[m]) {
			r = m
		} else {
			l = m + 1
		}
	}
	return l
}

Practice in the Vault

Looking to solidify your understanding? Head over to the Problem Vault to solve curated problems related to this module with detailed walkthroughs and optimal solutions.

Next Steps

Continue to 11 Graphs where ordering and frontier expansion become graph traversal primitives.