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 $\backslash$Theta $($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 $\backslash$Theta $(1)$ time$).$

For example, consider the following array. Index; $0123456789101112$

A ; $3142731394255707481919398$

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 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 $\text{'}$v$\text{'}$ values assigned to you.