Algorithm Design and Analysis

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

$($You should have learned the Binary$-$Search algorithm in the CSC$307$ class.$)$

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

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

its solution.

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