$15\mathrm{.}14$ LAB: Binary Search

Binary search can be implemented as a recursive algorithm. Each call makes a recursive call on one$-$half of the list the call received as an argument.

Complete the recursive function binary$\_$search$()$ with the following specifications:

Parameters:

a list of integers

a target integer

lower and upper bounds within which the recursive call will search

Return value:

if found, the index within the list where the target is located

$-1$ if target is not found

The algorithm begins by choosing an index midway between the lower and upper bounds.

If target $==$ nums$[$index$]$ return index

If lower $==$ upper, return $-1$ to indicate not found

Otherwise call the function recursively with half the list as an argument:

If nums$[$index$]<$ target, search the list from index $+1$ to upper

If nums$[$index$]>$ target, search the list from lower to index $-1$

The list must be ordered, but duplicates are allowed.

Once the search algorithm works correctly, add the following to binary$\_$search$()$:

Count the number of calls to binary$\_$search$().$

Count the number of times when the target is compared to an element of the list. Note: lower $==$ upper should not be counted.

Hint: Use a global variable to count calls and comparisons.

The input of the program consists of integers on one line followed by a target integer on the second.

The template provides the main program and a helper function that reads a list from input.

Ex: If the input is:

$123456789$

$2$

the output is:

index: $1,$ recursions: $2,$ comparisons: $3$

$506456\mathrm{.}3611264.$qx$3$zqy$7$

LAB ACTIVITY

$15\mathrm{.}14\mathrm{.}1$: LAB: Binary Search

$8/10$

main.py

Load default template...

Develop mode

Submit mode

When done developing your program, press the Submit for grading button below. This will submit your program for auto$-$grading.

Submit for grading

Coding trail of your work

What is this?

$12/11$

M

$-$

R

$-$

$-$

$2$

M

$-$

$-$

$8$

T

$-$

$-$

$-$

$-$

$-$

$-$

$-$

$-$

$-$

min:$12$

Latest submission $-10$:$51$ AM KST on $01/15/24$

Total score: $8/10$

Download this submission

$1$:Compare output

$2/2$

Input

$123456789$

$2$

Your output

index: $1,$ recursions: $2,$ comparisons: $3$

$2$:Compare output

$2/2$

Input

$112233445566778899$

$11$

Your output

index: $0,$ recursions: $3,$ comparisons: $5$

$3$:Compare output

$0/2$

Output differs. See highlights below.

Input

$1015202530354045$

$50$

Your output

index: $-1,$ recursions: $4,$ comparisons: $6$

Expected output

index: $-1,$ recursions: $4,$ comparisons: $7$

$4$:Compare output

$2/2$

Input

$10202020202025303540455060$

$20$

Your output

index: $2,$ recursions: $2,$ comparisons: $3$

$5$:Unit test

$2/2$

Test binary$\_$search$()$ with $[11,22,33,44,55,66,77,88,99]$ and target $=99.$ Should return $8.$

Test feedback

binary$\_$search$()$ correctly returned $8$