Python Programming Objective Convert a looping algorithm to a recursive algorith

Question

Python Programming

Objective

Convert a looping algorithm to a recursive algorithm

Design

function name: binary_search_recursive

parameters: value you’re searching for

list you’re searching through (entire list)

left index of the sublist you’re currently searching

right index of the sublist you’re currently searching

returns: index of the value if found or -1 if not found

Implementation

Do not use list slicing

Testing

Create a list of 20 numbers (must be sorted). When testing, print the left index, right index, and middle index, and the values at those indices.

After you finish testing, comment out all testing print statements. The function should not print anything after testing is finished.

Timing

Time your recursive binary search

Time both looping and binary recrusive search

Explanation / Answer

import time

def bin_search(list,l,r,k):
      m = int(round((l+r)/2))
      print("-----------")
      print("L ",l)
      print("R ",r)
      print("M ",list[m])
      if k>list[r]:
         return -1
      if r-l == 1:
         if list[r] != k and list[l] != k:
            return -1
         if list[r] == k :
            return r
         if list[l] == k :
            return l
     
      if list[m] == k:
         return m
      if k > list[m]:
           return (bin_search(list,m+1,r,k))
      if k < list[m]:
           return (bin_search(list,l,m-1,k))

list = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]
print("Looking for 18")
start_time = time.time()
index = bin_search(list,0,19,18)
print("Returned index:",index)
print("--- %s seconds ---" % (time.time() - start_time))
print("Looking for 31")
start_time = time.time()
index = bin_search(list,0,19,31)
print("--- %s seconds ---" % (time.time() - start_time))
print("Returned index:",index)

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.