Algorithm Lab

Week $3$: Binary Search

Description

Binary search in a well$-$known divide and conquer algorithm. In original, binary search is designed for searching position of specific value in a sorted random$-$accessible list.

We can see an array $A=\{a_1,a_2,$dots,$a_n\}$ as a function $A^{\text{'}}(i)=a_i$ have domain $1,n.$ If array $A$ is an increasing$-$order array or a decreasing$-$order array, then the correspond function $A^{\text{'}}(i)$ is a monotone function. Thus, we can change the definition as followed:

Instance: A monotone function $f(x)V,$ a value vinV, and a precision $.$

Result: xinx that $v$ in range $f(x-),f(x+).$

In this version, we can not only find the specific value in a sorted array $($use $=1),$ but also solve an equation $y=f(x)$ where $y$ is the specific value and $f(x)$ is a monotone function.

Questions

$1$ Write pseudo code of binary search algorithm.

$2$ Analysis pseudo code of step $1.$

$2\mathrm{.}1$ Space complexity

$2\mathrm{.}2$ Time complexity in base case

$2\mathrm{.}3$ Time complexity in worst case