Example: binary search

int binSrch(int a[],int &n, int x)

{ //a[] is a sorted array of n elements

fst = 0; lst = n-1;

while (fst <= lst){

mid = (fst + lst)/2;

if (x == A[mid]) return mid;

if (x > A[mid]) fst = mid + 1;

else lst = mid -1;

}

return -1;

}

A recurrence relation: T(n) ? T(n/2) + c1

T(0) = c2

Previous slide

Next slide

Back to first slide

View graphic version