Consider the searching problem:

Input: A sequence of n numbers A=a1,a2,,an and a value v.

Output: An index i such that v=A[i] or the special value NIL if v does not appear in A.

1. Write the pseudocode for linear search, which scans through the sequence, looking for v. State the asymptotic bound of its running time, and briefly explain why.
2. If the sequence A is sorted, we can check the midpoint of the sequence against v and eliminate half of the sequence from further consideration. The binary search algorithm repeats this procedure, halving the size of the remaining portion of the sequence each time. Write the pseudocode for binary search, either iterative or recursive.
3. Write the recurrence of binary search algorithm, and then use master theorem to find its solution.