3. Write the function find sorted elt whose input is a vector sorted in increasing order and an element

x. The output is 0 if the element x does not occur in v, 1 if the element x does occur in v. Below is the

algorithm you should implement, known as the binary search algorithm. Note that the code below

returns the index, but we want to return true or false, not the index, so adjust your code accordingly.

Algorithm. Given an array A of n elements with values or records A1, . . . , An and target value T, the

following subroutine uses binary search to find the index T in A.

(a) Set L to 1 and R to n.

(b) If L > R, the search terminates as unsuccessful. Set m (the position of the middle element) to

the floor of (L + R)/2.

(c) If Am < T, set L to m + 1 and go to step 2.

(d) If Am > T, set R to m 1 and go to step 2.

(e) If Am = T, the search is done; return m.

Comparing an element of v to x (either with == or with <) counts as one step. Setting the output

value, setting the value of n, setting the value of i, all also count as one step.

(a) How many steps does it take for the input of v=[2, 5, 6, 7, 9, 10, 11, 12] and x = 7? List each step in order.

(b) Give an example of an unsorted vector v and an element x in v for which the algorithm would

return an answer of 0.

(c) Whats the most number of steps it could take for a length 8 input?

(d) Estimate the most number of steps it could take for a length 1000 input? Explain.