solution_008.py

#!/usr/bin/python3
# ===================================================================
# Binary search a sorted list - find an entry (if it exists)
# A better way is to re-phrase the question so there is always only
# one answer ("If I was going to add another 7 to the list, where
# should I put it so it is the first 7") 
# -------------------------------------------------------------------
# from: www.youtube.com/watch?v=tgVSMA8j0Q
#       Binary search - A Different Perspective
# -------------------------------------------------------------------
# Note: '//' rounds down
# ===================================================================

# -------------------------------------------------------------------
# ---- binary search, find element if it exists
# ---- return array index or -1
# -------------------------------------------------------------------

def binary_search(ary,x):

    if  len(ary) < 1:
        return -1

    lo = 0                     # lower bound
    hi = len(ary)              # upper bound

    # increase the lower bound and decrease the upper bound
    # until they are equal

    while lo < hi:

        mid = (lo + hi)//2     # another way is: lo + (hi-lo)//2

        if ary[mid] < x:
            lo = mid + 1
        else:
            hi = mid

    if lo != len(ary) and ary[lo] == x:
        return lo

    return -1

# -------------------------------------------------------------------
# ---- test the binary search and display the results
# -------------------------------------------------------------------

def test_binary_search(ary,x):

    i = binary_search(ary,x)

    print(f'search list: {ary}')
    print(f'search for : {x}')
    print(f'returned index is {i}')
    if i < 0:
        print('not found')
        ##raise valueError
    print()


# -------------------------------------------------------------------
# ---- main
# -------------------------------------------------------------------

if __name__ == '__main__':

    # ---------- test data

    lst1 = [2,3,3,4,7,7,8,9]
    lst2 = []
    lst3 = [7]

    print()

    # ---------- first problem

    test_binary_search(lst1,7)

    # ---------- second problem

    test_binary_search(lst1,6)

    # ---------- third problem

    test_binary_search(lst2,7)

    # ---------- forth problem

    test_binary_search(lst3,7)

    # ---------- fifth problem

    test_binary_search(lst1,2)

    test_binary_search(lst1,1)

    # ---------- sixth problem

    test_binary_search(lst1,9)

    test_binary_search(lst1,10)