🎁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

The tared mass of a sample is its mass without regard to its container Transfer liquids and solutions from a reagent bottle or beaker with the aid of a stirring rod. 20. 21. womnD A small est tube has a volume of -3 mL. 23. A litmus paper test for the acidity or basicity of a solution requires the use of a stirring rod to remove a portion of the solution to then be touched to the litmus paper After drying a hygroscopic solid in a drying oven, the solid should be cooled in a desiccator. The color change of the indicator at the endpoint of a titration should persist for 30 seconds. 24. 25. Answer True or False for the following statements that refer to Laboratory Techniques. Ask your instructor to identify the questions you are to complete. 1. All clean glassware should be air-dried naturally 2. While cleaning glassware, discard all washes and rinses from the delivery point of the glass vessel. 3. To avoid waste in the use of chemicals, share the unused portion with other chemists before discarding. 4. Never touch, taste, or smell a chemical unless specifically told to do so. 5. A chemical with a "blue hazard label (a number 3 rating) means that the chemical is highly reactive. -6. If uncertain as to how to dispose of a chemical, dumping it into the sink followed by copious amount of - water is a safe disposal procedure. 7. Use a spatula to transfer solid chemicals from a reagent bottle. 8. Most all chemicals used in experiments can be disearded into the sink. 9. The number of significant figures used to record the mass of a chemical should correspond to the sensitiv- ity of the balance used for the measurement. 10. A 3-inch test tube has a volume of 3 ml.; an 8-inch test tube must have a volume of 8 ml. 11. To transfer a solution, a stiring rod touches the delivery point of the reagent vessel and the wall of the receiving vessel. 12. The minimum number of centrifuge tubes placed in a centrifuge during its operation is two. 13. A test tube should be less than one-third full when heating with a "cool" flame. 14. Right-handed students should operate the stopeock of a buret with their left hand and swirl the Erlenmeyer (receiving) flask with the right hand. 15. The thumb is the digit of choice on controlling the flow of liquid from a pipet. 16. Blow out the solution remaining in the pipet tip after the solution has drained from the pipet 17. A buret must always he filled to the top (the zero mark) before every titration procedure. 18. The volume of solution in a buret should be read and recorded 10-15 seconds after completing the titration. -19, It is possible to add a half-drop of solution from a buret. 20. To test the acidity of a solution with pH paper, place the pH paper directly in the solution. 21. The odar of a chemical should not be tessed unless specifell instructed to do so. The vapors of the chem- 22. One must first calculate the number of moles of solute that are required before preparing a solution of ical should be fanned toward the nose. known concentration. Summarize the Disclaimer in your own words. 42 Laboratory Techniques

<p dir="ltr">what type of passage is Frankenstein? please help for teas</p>

س 1) أجب ما يلي نقطة 20 A) The variation of the power and is as shown in Figure (1) The uncionarstal fuel cost of two tatal at spired by ht ۴ a) Express the power demand as a tinction of the b Far optional economic operation, find a P, and, at time dpm 012F TQDMWinr imit +2=۔ و 0.015F IQmMin +15 - Figun (1) اضف مافه

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.

<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>