3 / 3 Divide and Conquer

The Half That Never Shrinks

int a[] = {4, 9, 2, 7};

int best(int l, int r) {              // maximum of a[l..r], both ends included
    if (l == r) return a[l];
    int mid = (l + r) / 2;
    return max(best(l, mid), best(mid, r));
}

cout << best(0, 3);

What happens when this runs?

A

It reads a[4] and the result is undefined.

B

It recurses forever and overflows the stack.

C

It prints 9, but visits every element twice.

D

It prints 7, because index 1 never reaches the right half.