Chapter 12 (pp. 211–246) of Computer Science I.

Topics

Key Ideas

• Binary search requires sorted data; O(log n) vs linear O(n).
• Sort tradeoffs: selection/insertion O(n²) simple; quick/merge O(n log n).
• Comparators decouple ordering from the sort — realized as function pointers in C, Comparator/lambdas in Java, comparator functions in PHP.
• Practical pitfalls: arithmetic overflow in midpoint ((lo+hi)/2), the unsafe “difference trick” in comparators, need for a total order, and sort stability.
• Analysis ties back to basics numerical errors.

Examples

Binary search (sorted input)

lo ← 0
hi ← length(A) - 1
while lo ≤ hi:
  mid ← lo + (hi - lo) / 2     // avoids overflow of (lo + hi)
  if A[mid] = target: return mid
  if A[mid] < target: lo ← mid + 1
  else: hi ← mid - 1
return -1

Selection sort

for i from 0 to n - 2:
  min ← i
  for j from i + 1 to n - 1:
    if A[j] < A[min]: min ← j
  swap A[i], A[min]

O(n²), but simple and in-place.

In Java

static int binarySearch(int[] a, int target) {
    int lo = 0, hi = a.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;   // avoids overflow of (lo + hi)
        if (a[mid] == target) return mid;
        if (a[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

For production code prefer Arrays.sort / Collections.sort with a Comparator — see the Java part.

Citations

[1] Computer Science I, Ch. 12, pp. 211–246.