Let A[1..n] be an array containing distinct integers sorted in increasing order.

ID: 3694807 • Letter: L

Question

Let A[1..n] be an array containing distinct integers sorted in increasing order. The following algorithm 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).

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).

Explanation / Answer

We need to prove the only thing that the given algorithm returns the index of number if numberarray, or 0 if numberarray. We will now prove it by induction, where n=rightleft+1. We have to show that at each step it preserves the invariant.

CASE-1 : When number exists in the given sorted array

Base case : if n=1, since this is the only number, it is returned as the searched number exists in the array.

Inductive step :
Generally speaking, it doesn't matter whether the number is on left side or right side. All that matters is that the algorithm should do next iteration on a strictly smaller sub array.
   1. If number=array[middle]. This works correctly.
   2. If number<array[middle], then since it occurs in array atleast once, and the array is sorted, it must occur at a position between array[left] to array[middle-1]. Therfore, the invariant is preserved if we recur on array[left....(middle1)]
   3. If numberarray[middle], then since it occurs in array atleast once, it must occur at middle or later position. And therefore, the invariant is preserved if we recur on array[middle..rigth]

CASE-2 : When number doesn't exists in the given sorted array
when the s<=1 it will return false. it means the number of element in the subarray is zero and the number that we are searching will not be present in the subarray.

Navigate

Let A[1..n] and B[1.n] be two arrays sorted in increasing order. Assume that bot

Let A[1..n] be an array containing n distinct real numbers (some of these may be

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

Let A[1..n] be an array containing distinct integers sorted in increasing order.

Question

Explanation / Answer

Related Questions

Navigate