Show all work for part a and b.

3. (intermediate) Observe that if the sequence A is sorted, we can check the midpoint of the sequence against v (the element we're looking for) 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. The following is a recursion-based pseudo-code is supposed the following: returns an index i such that psi srand A[i] = v if such an index exists, and returns -1 otherwise. Prove the correctness via induction. BSearch(A, p, r, v) If r