228k views
0 votes
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; }

1 Answer

4 votes

Answer:i think the answer is l=

0

Step-by-step explanation:

User Tom Brock
by
6.3k points