Computers and Technology

Janessa Campbell

28 August, 20:53

Prove the correctness of Binary Search through the use of a loop invariant (which you should prove by induction). Assume that a is sorted, and that n is the number of elements in a. int BinarySearch (int * a, int n, int x) { int L = 0, r = n-1; while (L < = r) { int m = (L+r) / 2; if (a[m] = = x) return m; if (a[m] < x) L = m+1; else r = m-1; } return - 1; }