Analysis of Algorithms 1. Using Loop Invariant, Prove that if data is sorted and

Question

Analysis of Algorithms

1. Using Loop Invariant, Prove that if data is sorted and data[x] = t, then lo < x <=(less than or equal to) hi after every iteration of the while loop in the BinSearch algorithm above.

Input: data: sorted array of n integers Input: n: size of data Input: t: an integer Output: index x such that datalx-t, or 0 if t data 1 Algorithm: BinSearch 210-0 4 while hi - lo > 1 do m2 if data[mid] = t then return t else if data mid hi mid 7 s else if data[mid > t then 9 1 else lo = mid 12 end 13 end 14 if datalhij t then 15 return hi 16 else 17return 0 18 end

Explanation / Answer

if we observe the algorithm:

in step 15 : hi value is returned and in step17: 0 is returned, means the x value is either hi(value in hi variable) or 0

now given that data[x]=t;

means t is present at location x, that means x can't be 0

so x value must be <=n

where hi value is set initially to n

so, x<=hi in every iteration, because in every iteration x is taken as mid value, so it must be less than or equal to hi

now,..loop variant is hi-lo > 1

hi > lo+1

we already said that x value is the mid value in the array, means it must be greater than lo

so,...lo<x<=hi

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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