Consider the following search algorithm:

procedure binary search(x, L=a1,,an; a1an) i := 1 j := n while (ij) m := if x = am then return m else if x then j := m - 1 else i := m + 1 end while return -1

Prove that the algorithm correctly returns a value k where x = ak or it returns -1 if there is no such k.

di