Problem $7$: Binary Search

In this problem, you will write a function named binary$\_$search$()$ with two parameters x and item. The parameter x

should be a list containing elements with a single data type, and that is assumed to have been sorted in increasing order.

The parameter item should contain a value of the type that is contained in x$.$

The function will apply a divide$-$and$-$conquer technique to recursively search the list x for an occurrence of the value stored

in item. The function should return True if item is found in x$,$ and should return False otherwise.

Write a function binary$\_$search$()$ that accepts two parameters named x and item.

The function should return a boolean value indicating if item was found in x by performing the following steps:

$1.$ First check if item is less than the first element of x or greater than the last element of x$.$ Since x is assumed to

be sorted, if either of these conditions are true, then item is not in x and you can return False.

$2.$ We split the list x into two pieces by selecting an element in the middle of the list. Create a variable named mid

that is equal to the length of x divided by $2,$ rounded down. Use int$()$ to coerce the result into an integer.

$3.$ If item is equal to x$[$mid$],$ return True.

$4.$ If item is less than x$[$mid$],$ then item would have to be in the first half of x $($if it is there at all$).$ Slice out the

elements of x up to the index mid, pass this sub$-$list and item to binary$\_$search$(),$ and return the result.

$5.$ If item is greater than x$[$mid$],$ then item would have to be in the last half x $($if it is there at all$).$ Slice out the

elements of x after the index mid, pass this sub$-$list and item to binary$\_$search$(),$ and return the result.

We will now test this function.

In a new code cell, create a randomly generated list using the following lines of code:

random.seed$(1)$

random$\_$list$\_1=$ sorted$($random$.$choices$($range$(100),$ k$=100))$

Use a loop to search random$\_$list$\_1$ for each integer $09.$ Print the results of each search in the following format:

N $-$ XXXX

The character N should be replaced with the integer being search for and the characters XXXX should be replaced with

either True or False.