Python3

Idea of the Binary Search algorithm: Binary Search finds a number (or report that it does not exist) in a sorted sequence of numbers For example, we will search for number 7 in [2, 4, 7, 9, 12, 15, 20] 1. You start checking the middle element, which is 9 2. Then you check whether the number you are looking for (7 in our case) greater (or equal to), or less than the middle element (which is 9) If they are the same. You report success and exit. (7 does not equal 9 in our case) If the number to find is smaller than the middle element, then you move to the first half of the sequence (smaller numbers). This our case. If the number to find is larger then the middle element, then you move to the second half of the sequence (larger numbers) 3. Repeat step 1: Check the middle element of the smaller sequence [2, 4, 7. It is 4. 4. Repeat step 2. 5. Since your sequence is getting smaller and smaller with each iteration, eventually you will have only two possible outcomes You find the number you are looking for and report that the number was found Your number is not there, the size of the sequence is 0 and you report that the number is not there. For lists of even size, the middle index is the previous of the two middle elements. For example, if the given list is 0, 1, 2, 3], then the middle element would be 1 and not 2. However there is a twist in this problem. You are given a list of numbers sorted in ascending order and a target value to find. Write a function binary search insert that takes in this sorted list, target value to find and . returns the index of the target value to find if it is found in the given list. return the index the value would be at if it were inserted in order, if to_find is not found in the given list. arr [1, 4, 5, 7] binary_search insert(arr, 5) binary_search insert(arr, 6) binary_search_insert (arr, -1)