(a) Draw the “Tree of Probes” for Linear Search when n = 7. (b) Draw the “Tree of Probes” for Binary Search when n = 14 and n = 20. Prove by MI that for all k 2 {0.. }, if Binary Search is applied to...

(a) Draw the “Tree of Probes” for Linear Search when n = 7.

(b) Draw the “Tree of Probes” for Binary Search when n = 14 and n = 20.

Prove by MI that for all k₂
{0.. }, if Binary Search is applied to an array of length n and has not terminated after k (unsuccessful) probes, then the length of the current sub list must be

Why does every entry in A appear exactly once in the tree of Probes for Binary Search?

Do other loop invariants hold for Binary Search? Prove that:

(a) Either p = 1 or A[p - 1] <>

(b) Either q = n or T <>