Prove that if data is sorted and data[x] = t, then lo < x hi after every iterati

Question

Prove that if data is sorted and data[x] = t, then lo < x hi after every iteration of the while loop in the BinSearch algorithm.

Please provide explanation and steps taken when completing proof.

Input: data: sorted array of n integers Input: n: size of data Input: t: an integer Output: index x such that data[x-t, or 0 if t ¢ data 1 Algorithm: BinSearch 210 = 4 while hi-lo 1 do mid =(hi + lo)/2] if data!mid t then 7 return t else if data!mid t then 9 10else lo mid 12 end 13 end 14 if datalhi]-t then 15return ha 16 else 17return 0 18 end

Explanation / Answer

Prove is done using induction.

Base Case:

When the while loop of the algorithm begins, then lo=0 and hi=n. Since the index of all the elements of the array is greater than lo=0 and not more hi=n,so the taget index x will also be greater than lo=0 and less than or equal to hi=n.

Inductive Hypothesis:

Suppose at any iteration of the loop lo < x hi holds true.

Inductive Step:

ceil is the ceiling function,i.e., ceil(1.8) = 2 ,ceil (1.2) = 2 ,ceil(1.5) = 2 etc.

mid = ceil ((lo + hi)/2) = ceil( (lo + (hi-low)/2) ) = lo+ceil ( (hi-lo)/2 ) > lo because (hi-low)>1 is the condition of while loop

=> mid > lo

Also, mid = ceil ((lo + hi)/2) = ceil( (hi - (hi-low)/2) ) = hi-ceil ( (hi-lo)/2 ) < hi because (hi-low)>1 is the condition of while loop

=>mid < hi

Now three cases are possible:

Case 1: If data[mid] = t then,

loop ends because of return statement and the returned value of x=mid<hi and x=mid > lo.

So, lo < x hi (inductive hypothesis is true)

Case 2: If data[mid] > t then the target t must be between data[lo] and data[mid].

In this case we update hi = mid.

So , before this inductive step lo<x<=hi and now hi gets updated to mid>lo and data[x]=t<data[mid]

=> x still holds the inductive hypothesis lo < x hi.

Case 3: If data[mid] < t then the target t must be between data[mid] and data[hi].

In this case we update lo = mid.

So , before this inductive step lo<x<=hi and now lo gets updated to mid<hi and data[mid]< t = data[x]

=> x still holds the inductive hypothesis lo < x hi.

So in all the above cases we either preserve the inductive hypothesis for next loop or the loop gets end.

So this proves that lo < x hi after every iteration of the while loop.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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