// Find max value in a[n] maxVal = maxi(a, 0, n-1); // Find max in array slide a[lo..hi] int maxi(int a[], int lo, int hi) { int maxL, maxR, mid; if (lo == hi) return a[lo]; mid = (lo+hi)/2; maxL = maxi(a, lo, mid); maxR = maxi(a, mid+1, hi); return (maxL > maxR) ? maxL : maxR; }
Cost: O(n) (same as linear scan)