Problem 2: Recursive Binary Search Write a recursive function binary_search that takes an ordered array of numbers a and a number to search for n as parameters and returns the index of the first occurrence of the number in the array, or -1 otherwise. For full credit, the search should be implemented using recursion, rather than a loop. Given a = [-1, 1, 3, 5, 7, 9]: Example call Returns linear_search(a, 1) 1 linear_search (a,0) -1 linear_search(a, -1) 0 linear_search(a, 2) -1 linear_search(a, -2) -1 linear_search(a, 4) -1
binary_search.py 1 # MODIFY ME TO IMPLEMENT YOUR SOLUTION 2 # TO PROBLEM 2: Recursive Binary Search 3 # 4 # NAME: FIXME 5 # ASSIGNMENT: Technical HW: Sorting & Searching 6 7 # Write a recursive function 'binary_search that 8 # takes an ordered array of numbers as a parameter 9 # and a number to search for and returns the index 10 # of the number in the array, or -1 otherwise. For 11 # full credit, the search should be implemented using 12 # recursion, rather than a loop. 13 def binary_search(array, num): 14 | return search(array, num, 0, len(array) - 1) 15 16 def search(array, num, min, max): 17 TIT return -1 18 19 def main(): 20 a = [i for i in range(-1, 10, 2)] 21 print(a) 22 for n in (1, 0, -1, 2, -2, 4, 5, 6, 7, -67, 134]: 23 print("%5d index? %d" % (n, binary_search(a, n)) ) 24 main() 25
I'I binary_search_test.py From binary_search import binary_search 1 2 3 def test_empty(): assert binary_search([], 0) == -1 4 5 6 7 8 9 def test_1(): a = [-67, -44, -2, 33, 45, 67, 134] accont hinary_search(a, 1) == == -1 test_o() def test 0(): a = [-67, -44, -2, 33, 45, 67, 134] assert binary_search(a,0) == -1 10 11 12 13 14 15 def test__1(): a = [-67, -44, -2, 33, 45, 67, 134] assert binary_search(a, -1) == -1 16 17 18 19 def test_2(): a = [-67, -44, -2, 33, 45, 67, 134] assert binary_search(a, 2) == -1 20 21 22 23 def test_2(): a = [-67, -44, -2, 33, 45, 67, 134] assert binary_search(a, -2) == 2 24 25
binary_search_test.py - 3 3 25 26 def test_134(): 27 a = [-67, -44, -2, 33, 45, 67, 134] 28 assert binary_search(a, 134) == 6 29 30 def test_67(): 31 a = [-67, -44, -2, 33, 45, 67, 134] 32 assert binary_search(a, 67) == 5 33 34 E def test__67(): 35 a = [-67, -44, -2, 33, 45, 67, 134] 36 assert binary_search(a, -67) 37 38 E def test_first(): 39 a = [1, 1, 1, 2, 2, 2, 2, 2, 2] 40 assert binary_search(a, 2) == 3 41 42 E def test_first1(): 43 a = [1, 1, 1, 2, 2, 2, 2, 2, 2] 44 assert binary_search(a, 1) == 0 45 46 def test_last(): 47 a = [1, 1, 1, 2, 2, 2, 2, 2, 2, 3] 48 assert binary_search(a, 3) == 9 49 5 50