6. (6 points) Let A[1..n] be an array containing n distinct integers sorted in i

Question

6. (6 points) Let A[1..n] be an array containing n distinct integers sorted in increasing order, where n 1. The following algorithm from page 364 of the text determines if a query integer x is in A; it returns the position of x in A if x is present and returns zero otherwise. The initial call is Binary-Search(1, n, x).

1. Binary-Search(i,j,x) // Search subarray A[i..j] for x, 1 <= i <= j <= n

2. m <- floor((i+j)/2)

3. if (x = A[m]) then return(m)

4. else if (x < A[m] and i < m) then return(Binary-Search(i,m-1,x))

5. else if (x > A[m] and j > m) then return(Binary-Search(m+1,j,x))

6. else return(0)

7. end

Let P(s) be the assertion that when presented with a subarray A[i..j] of size s = j i + 1, Binary-Search(i, j, x) returns the position of x in A[i..j] if x is present in the subarray and returns zero otherwise, 1 i j n. Use Strong Induction to prove that P(s) is true for s 1. Similar to recursive linear search (discussed in class) consider separately the cases where x is present/not present in the subarray being searched (A[i..j] here).

The question requires using Strong Induction so please have an answer using strong induction

Explanation / Answer

Let P(n) be the assertion that Binary-Search works correctly for inputs where j-i = n.
If we can prove that P(n) is true for all n, then we know that Binary-Search works on all possible arguments.

Base Case:
In the case where n=0, we know i=j=m. Since we assumed that the function would only be called when x is found between i and j,
it must be the case that x = a[m], and therefore the function will return m, an index of x in array a.

Inductive Step:
We assume that Binary-Search works as long as i-j k.
Our goal is to prove that it works on an input where i-j = k + 1. There are three cases, where x = a[m], where x < a[m] and where x > a[m].

Case x = a[m]
Clearly the function works correctly.

Case x < a[m]
We know because the array is sorted that x must be found between a[i] and a[m-1].
So if the recursive call works correctly, this call will too.
The n for the recursive call is n = m 1 i = (i+j)/2 1 i.
If i+j is odd, then n = (i + j 1)/2 1 i = (j i)/2 1, which is definitely smaller than ji.
If i+j is even then n = (i + j)/2 1 i = (ji)/2, which is also smaller than k + 1 = ji because ji = k + 1 > 0.
So the recursive call must be to a range of a that is between 0 and k cells, and must be correct by our induction hypothesis.

Case x > a[m].
This is more or less symmetrical to the previous case. We need to show that r (m + 1) j i.
We have r (m + 1) l = j (i + j)/2 1. If j+i is even, this is (ji)/2 1, which is less than ji.
If j+i is odd, this is j (i + j 1)/2 1 = (ji)/2 1/2, which is also less than ji.
Therefore, the recursive call is to a smaller range of the array and can be assumed to work correctly by the induction hypothesis.

Because in all cases the inductive step works, we can conclude that Binary-Search (and its iterative variant) are correct.

Related Questions

Navigate

• Browse (All)
• Browse 6
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.