Analysis of Algorithms

1. Using Loop Invariant, Prove that if data is sorted and data[x] = t, then lo

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