q32KpsUtprac.py

# aahnik 2020
def recursive_binary_search(arr, lo, hi, ele):
    # Returns index of ele in arr if present, else -1
    # arr is our list
    # lo is lower/left pointer
    # hi is higher/right pointer
    # ele is element to search

    if hi >= lo:
        # possibility that ele exists
        mid = lo + (hi - lo) // 2

        if arr[mid] == ele:
            # base case
            return mid
        elif arr[mid] > ele:
            # search ele in left portion
            return recursive_binary_search(arr, lo, mid - 1, ele)
        else:
            # search ele in right portion
            return recursive_binary_search(arr, mid+1, hi, ele)
    else:
        # ele is not present in list
        return (- 1)


def binary_search(my_list, to_search):
    # perform binary search on my_list to find to_search
    index = recursive_binary_search(my_list, 0, len(my_list), to_search)
    if index == -1:
        print(f"{to_search} not found")
        return False
    else:
        print(f"{to_search} found in index {index}")
        return True


    

test_soln.py

from q32KpsUtprac import binary_search, recursive_binary_search


def test_recursive_binary_search():
    my_list = [1, 3, 5, 6, 7, 8, 9, 12, 23, 27]
    to_search1 = 6
    to_search2 = 4

    index1 = recursive_binary_search(my_list, 0, len(my_list), to_search1)
    index2 = recursive_binary_search(my_list, 0, len(my_list), to_search2)

    assert index1 == 3
    assert index2 == -1


def test_binary_search():
    example_list = [1, 3, 5, 6, 7, 8, 9, 12, 23, 27]
    to_search1 = 6
    to_search2 = 4
    assert binary_search(example_list, to_search1)
    assert not binary_search(example_list, to_search2)

OUTPUT
6 found in index 3
4 not found