Question

Task 2: Recursive Binary Search Part A - Target in list? Write a function simple recursive binary search(lst, target) which returns True if target is in lst; otherwise False. You must use recursion to solve this problem (i.e. do not use any loops).

Part B - Where is target? Write a function advanced recursive binary search(lst, target, lo, hi) which returns the index of an instance of target in lst between lo and hi, or None if target is not in that range. When first calling the function, lo = 0 and hi = len(lst)-1. You must use recursion to solve this problem (i.e. do not use any loops).

PYTHON CODE

Answer 1

Check the Image for Indentation, In both the problem . RECURSION WAS USED

def BinarySearchRecursive(lst, target):

    if len(lst) == 0:

        return False

    else:

        middle = len(lst)//2

        if (target == lst[middle]):

            return True

        else:

            if target > lst[middle]:

                return BinarySearchRecursive(lst[middle+1:],target)

            else:

                return BinarySearchRecursive(lst[:middle],target)

------------------------------------------------------------------------------------------------------------------------------------

def BinarySearch(lst,target, lo, hi):

    if hi < lo: return -1     

    mid = (lo + hi)   

    if target == lst[mid]:

        return mid             

    elif target < lst[mid]:

        return BinarySearch(lst, target, lo, mid - 1)

    else:

        return BinarySearch(lst, target, mid + 1, hi)

my_list=[1,5,9,10,55]   

print(my_list)

print("Index at",BinarySearch(my_list,1,0,4))

print(BinarySearchRecursive(my_list,1))

------------------------------------------------------------------------------------------------

SEE CODE FOR INDENTATION

Thanks, PLEASE COMMENT if there is any concern. PLEASE UPVOTE