Algorithm Design and Analysis

$(1)$ Use a figure to illustrate the operations of the Binary$-$Search algorithm.

$(2)$ Write pseudocode of the Binary$-$Search algorithm.

$(3)$ Write the recurrence relation of binary search and guess an asymptotic upper bond on

its solution.

$(4)$ Using the substitution method to prove your answer of the asymptotic upper bond.