[prev] 59 [next]

Finding Maximum in an Array

// 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)