Given a sorted array A[0...n-1] of n integers and a key v, develop a binary search algorithm that will determine the smallest index j (0 < j n-1) in the array such that v < A[j] in (logn) time. If v < A[0] or v A[n-1], there is no need to run binary search, you can check this before the beginning of your binary search algorithm and simply terminate (i.e., in (1) time). For example

Index 0 1 2 3 4 5 6 7 8 9 10 11 12

Number 3 14 27 31 39 42 55 70 74 81 91 93 98

If v = 40, your binary search algorithm should output the smallest index j for which v < A[j] to be 5.

If v = 42, your binary search algorithm should output the smallest index j for which v < A[j] to be 6.

If v = 3, your binary search algorithm should output the smallest index j for which v < A[j] to be 1.

If v = 97, your binary search algorithm should output the smallest index j for which v < A[j] to be 12.

If v < 3, your algorithm should simply terminate without running binary search. If v 98, your algorithm should simply terminate without running binary search. (a) Write the pseudo code of your algorithm as well as clear specify the invariants (properties) of the left index (LI) and the right index (RI) and explain how they are moved in each iteration. Also, explain when does your algorithm terminate and how do you identify the smallest index j for which v < A[j] by then.

(b) Show the execution of your algorithm on the array and the 'v' values assigned to you. Given

Index 0 1 2 3 4 5 6 7 8 9 10 11

Number 11 25 25 57 68 72 75 79 86 92 97 99

v values assigned are : 11 97 57 70