# NOTE: This implementation of insertion sort is provided for you.

# NOTE: DO NOT EDIT THIS FUNCTION IN THIS FILE.

def insertion$\_$sort$($arr$)$:

# Set index to $1$ for the outer loop.

index $=1$

# The outer loop steps the index variable through

# each subscript in the list, starting at $1.$ This

# is because element $0$ is considered already sorted.

while index $<$ len$($arr$)$:

# The first element outside the sorted subset is

# arr$[$index$].$ Assign the value of this element

# to unsorted$\_$value.

unsorted$\_$value $=$ arr$[$index$]$

# Start the scan variable at the subscript of the

# first element outside the sorted subset.

scan $=$ index

# Move the first element outside the sorted subset

# into its proper position within the sorted subset.

while scan $>0$ and arr$[$scan $-1]>$ unsorted$\_$value:

arr$[$scan$]=$ arr$[$scan $-1]$

scan $=$ scan $-1$

# Insert the unsorted value in its proper position

# within the sorted subset.

arr$[$scan$]=$ unsorted$\_$value

# Increment index.

index $=$ index $+1$

# NOTE: This implementation of binary search is provided for you!

# NOTE: DO NOT EDIT THIS FUNCTION IN THIS FILE.

def binary$\_$search$($arr$,$ value$)$:

# Set the initial values.

first $=0$

last $=$ len$($arr$)-1$

position $=-1$

found $=$ False

# Search for the value

while not found and first $<=$ last:

# Calculate the mid point.

middle $=$ int$(($first $+$ last$)/2)$

# If the value is found at the mid point...

if arr$[$middle$]==$ value:

found $=$ True

position $=$ middle

# else if value is in the lower half...

elif arr$[$middle$]>$ value:

last $=$ middle $-1$

# else if value is in the upper half...

else:

first $=$ middle $+1$

# Return the position of the item, or $-1$

# if it was not found.

return position

# TODO: We want to run binary search on this list to find a certain element.

# But something is wrong with this list that prevents us from doing that.

# Do you know what it is$?$ You should fix that first.

test$\_$list $=[1,2,8,9,45,65]$

# TODO: Once you have "fixed" the list so that you can run binary search on it$,$

# you should find the index of this target number.

# HINT: Look at the functions defined in this file.

target$\_$number $=45$

binary$\_$search$($target$\_$number$)$

print$("$Found at this index in fixed list: $")$

# TODO: Print the index of $`$target$\_$number$`$ in the $**$fixed$**$ list. You

# just need to print the number below. That's it$.$