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; }
