Divide and conquer

Overview

Divide and conquer is recursion where each call discards a fraction of the problem rather than a single element. Binary search halves the search interval every step, finding an element among a million in about twenty comparisons — provided the array is sorted, which is the precondition that makes the whole thing work. The companion example, counting subsets, shows the opposite side of the same coin: each element doubles the possibilities, so the count is 2^n. One recursion shrinks by half, the other grows by double, and comparing them builds intuition for why logarithmic and exponential sit at opposite ends.

Why it matters

Binary search is everywhere below the surface — database indexes, bsearch, version bisection in git, finding an insertion point, and any "find the boundary" query. It is also famously easy to get wrong: the classic overflow bug in (lo + hi) / 2 survived in widely used libraries for years, which makes it a good lesson in why the obvious expression is not always the safe one.

Core concepts

The sorted precondition. Binary search is only valid on sorted data. On unsorted input it does not merely run slower — it returns wrong answers, silently.

Halving the interval. Compare the middle element with the target: equal means found; the target being smaller means it can only be in the left half; larger means the right half. Each step discards half the remaining range, giving O(log n).

Compute the midpoint safely. lo + (hi - lo) / 2 rather than (lo + hi) / 2. For large indices the naive sum overflows, producing a negative midpoint and an out-of-bounds access — a real bug that shipped in production libraries.

The base case is an empty range. lo > hi means the element is absent. Getting this condition wrong is the difference between terminating and looping forever.

Inclusive bounds. With hi = n - 1 and the lo > hi termination, the range [lo, hi] is inclusive on both ends; the recursive calls must therefore use mid - 1 and mid + 1, never mid, or the range never shrinks.

The doubling counterpart. pset(n) = 2 * pset(n-1) counts subsets: each element is either in or out. That is 2^n — the growth rate that makes brute-force subset search infeasible past roughly 25 elements.

Syntax notes

/* binary search over the INCLUSIVE range [lo, hi]; array must be sorted */
int bs(const int *a, int lo, int hi, int t) {
    if (lo > hi) return -1;                 /* empty range - not found */
    int m = lo + (hi - lo) / 2;             /* overflow-safe midpoint */
    if (a[m] == t) return m;
    return (a[m] > t) ? bs(a, lo, m - 1, t) /* discard the right half */
                      : bs(a, m + 1, hi, t);/* discard the left half  */
}

/* number of subsets: each element doubles the possibilities */
long long pset(int n) {
    return (n == 0) ? 1 : 2 * pset(n - 1);
}

Key points:

• lo + (hi - lo) / 2 avoids the overflow that (lo + hi) / 2 risks.
• The recursive calls use m - 1 / m + 1; passing m again means the range never shrinks and the recursion never ends.
• pset needs long long, and even that only reaches n = 62.

Lesson

Binary search recursively discards half the array each step (O(log n)); counting a power set shows how each element doubles the possibilities (2^n). Both are recursion where the subproblem is a fraction of the original.

Code examples

#include <stdio.h>
static int bs(const int*a,int lo,int hi,int t){ if(lo>hi) return -1; int m=lo+(hi-lo)/2; if(a[m]==t) return m; return a[m]<t ? bs(a,m+1,hi,t) : bs(a,lo,m-1,t); }
static long long pset(int n){ return n==0 ? 1 : 2*pset(n-1); }
int main(void){
    int a[]={2,5,8,12,16,23,38,56,72,91};
    printf("index of 23 = %d\n", bs(a,0,9,23));
    printf("index of 17 = %d\n", bs(a,0,9,17));
    printf("a 10-element set has %lld subsets\n", pset(10));
    return 0;
}

Line by line

Common mistakes

Overflow in the midpoint; recursing on the wrong half; wrong 2^0 base case.

Debugging tips

Compiler errors and warnings:

• No warning for (lo + hi) / 2 overflow — it is well-formed code that misbehaves only at large indices.
• -Wsign-compare if indices are mixed signed/unsigned.

Runtime symptoms:

• Infinite recursion / stack overflow. The recursive call passes m instead of m - 1 or m + 1, so the range never shrinks.
• Returns -1 for an element that is present. The array is not actually sorted — check the precondition first.
• Crash on huge arrays. (lo + hi) overflowed to a negative midpoint. Use lo + (hi - lo) / 2.
• Off-by-one at the ends. The caller passed hi = n instead of hi = n - 1, so a[n] is read out of bounds.
• pset goes negative. Overflow past n = 62; that is the representable limit.

Technique: test an array of size 0, 1 and 2, plus targets that are smaller than everything, larger than everything, and absent from the middle. Those cases catch every boundary error.

Memory safety

• The midpoint overflow is a genuine memory-safety bug. (lo + hi) / 2 with large indices produces a negative value, and a[negative] is an out-of-bounds read. lo + (hi - lo) / 2 is the standard fix and costs nothing.
• hi must be n - 1. Passing n makes a[n] reachable — reading one past the end of the array.
• The sorted precondition is unchecked. Nothing in the code detects unsorted input; it simply returns wrong answers. Document it, and assert it in debug builds if the data comes from elsewhere.
• Depth is logarithmic, so the stack is never a concern here — unlike linear recursion.
• pset overflow. Signed overflow is undefined; bound n or use an unsigned type with a documented wrap.
• const int *a prevents accidental modification during the search.

Real-world uses

Concrete uses: Database B-tree lookups, the C standard library's bsearch, git bisect, finding an insertion point in a sorted array, and range queries in time-series data. The doubling counterpart explains why brute-force subset enumeration (knapsack, TSP by brute force) becomes infeasible around 25-30 elements, and therefore why the DP techniques in the previous track exist.

Professional best practices:

Beginner:

• Always use the overflow-safe midpoint, even for small arrays — the habit matters more than the case.
• Verify the array is sorted before searching.

Intermediate:

• Prefer the iterative binary search in production; it is equally clear and removes any stack concern.
• Learn the lower-bound / upper-bound variants (first index not less than the target) — they are more broadly useful than exact-match search.
• Use the 2^n growth as a design signal: if your algorithm enumerates subsets, look for a DP formulation instead.

Practice tasks

1. (Beginner) Recursive binary search. Implement int bs(const int *a, int lo, int hi, int t) with the safe midpoint. Example: target 23 in {2,5,8,12,16,23,38,56} -> index 5; a missing target -> -1. Concepts: halving, empty-range base case.

2. (Beginner) Count subsets. Implement long long pset(int n). Example: pset(3) -> 8. Concepts: doubling recursion.

3. (Intermediate) Count the comparisons. Instrument the search to count comparisons and confirm it is about log2(n) for arrays of 1,000 and 1,000,000 entries. Concepts: logarithmic behaviour.

4. (Intermediate) Lower bound. Implement a variant returning the first index whose value is >= t (the insertion point). Example: target 20 in the array above -> index 5. Concepts: boundary-finding binary search.

Summary

Divide and conquer discards a fraction of the problem at each step: binary search halves an inclusive range [lo, hi], terminating when lo > hi, and reaches any element of a million in about twenty comparisons — but only on sorted data, an unchecked precondition that silently produces wrong answers when violated. Compute the midpoint as lo + (hi - lo) / 2, because the obvious (lo + hi) / 2 overflows at large indices and turns into an out-of-bounds read. The subset-counting counterpart, 2 * pset(n-1), shows the opposite growth and explains why brute-force enumeration gives way to dynamic programming.

Practice with these exercises

• Recursive binary search
• Power set size