🎁BACK-TO-SCHOOL DEAL. Subscribe Now to get 40% OFF at only 8.49 USD/month, only valid until Sep 30th, 2024

Question

Question
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

Asked By EnchantedMoonlight99 at

Answered By Expert

Jeremy

Expert · 2.6k answers · 2k people helped

Sign in to see the answer

Hello, please find below the Python code for modified binary_search.py with search implemented in recursion.

 

def binary_search(array, num):
    return search(array, num, 0, len(array) - 1)

"""
search method implemented with recursion
"""
def search(array, num, min, max):
    if max >= min:
        mid = (min + max) // 2
        if array[mid] == num:
            return mid
        elif array[mid] > num:
            return search(array, num, min, mid - 1)
        else:
            return search(array, num, mid + 1, max)
    else:
        return -1


def main():
    a = [i for i in range(-1, 10, 2)]
    print(a)
    for n in [1,0,-1,2,-2,4,5,6,7,-67,134]:
        print("%5d index? %d" % (n, binary_search(a,n)))

main()

 

Just copy search method from above code, everything else is same.

 

Output Screengrab showing our search method is working fine with recursion :

[-1, 1, 3, 5, 7, 9]\n1 index? 1\n0 index? -1\n-l index? 0\n2 index? -\n-2 index? -\n4 index? -1\n5 index? 3\n6 index? -1\n7 index? 4\n-

 

If you have any doubt, let me know in comments. If not, please upvote the answer.

Thanks, Happy Learning!

🧑‍🏫 More Questions

Select all that are functions of neurons and glial cells Receive nerve impulses Protect neurons Nourish neurons Calcium storage

Consider the Hermiticity of the following operators. Prove that the momentum operator is Hermitian. For simplicity you may perform this proof for a one-dimensional system (i.e., only consider functions of x. and consider only the P operator). Is the operator d/dx Hermitian? Prove your answer. Is the operator d^2/dx^2 Hermitian? Prove your answer. Is the operator H = - h^2/2m d^2/dx^2 + V(x) Hermitian if V(x) is real? Prove your answer.

<div><div id="mobile-question-style" style="font-family: 'Helvetica Neue',Helvetica,Arial; color:#333333;">Reading passages for teas</div></div>

Which of the following describes the process of melting ice at room temperature? Enthalpy is favorable, Entropy is favorable Enthalpy is unfavorable, Entropy is favorable Enthalpy is favorable, Entropy is unfavorable Enthalpy is unfavorable, Entropy is unfavorable

<p>In what ways was Bacon's Rebellion a turning point in the history of the Chesapeake?</p> <p>Question 8 options:</p> <p>&nbsp;</p> <p>&nbsp;</p> <p>&nbsp;</p> <p>&nbsp;</p> <table summary=""> <tbody> <tr> <td> <p>&nbsp;</p> </td> <td> <p>&nbsp;</p> </td> </tr> <tr> <td> <p>a)&nbsp;</p> </td> <td> <p>The outcome of the rebellion encouraged elite Virginians to turn to enslaved West African labor over English indentured servants.</p> </td> </tr> <tr> <td> <p>&nbsp;</p> </td> <td> <p>&nbsp;</p> </td> </tr> <tr> <td> <p>b)&nbsp;</p> </td> <td> <p>It led to a fundamental restructuring and democratization of the colonial government.</p> </td> </tr> <tr> <td> <p>&nbsp;</p> </td> <td> <p>&nbsp;</p> </td> </tr> <tr> <td> <p>c)&nbsp;</p> </td> <td> <p>Charles II removed Governor Berkley, but otherwise little changed.</p> </td> </tr> <tr> <td> <p>&nbsp;</p> </td> <td> <p>&nbsp;</p> </td> </tr> <tr> <td> <p>d)&nbsp;</p> </td> <td> <p>Both a &amp; b.</p> </td> </tr> </tbody> </table>