find_first_binary_search.py

def recursive_binary_search(target, source, left=0):
    if len(source) == 0:
        return None
    center = (len(source) - 1) // 2
    if source[center] == target:
        return center
    elif target < source[center]:
        return recursive_binary_search(target, source[:center], left)
    else:
        return recursive_binary_search(target, source[center + 1:], left + center + 1)

'''
Find First
The binary search function is guaranteed to return an index for the element you're looking for in an array, 
but what if the element appears more than once?
Consider this array:
[1, 3, 5, 7, 7, 7, 8, 11, 12]
Let's find the number 7:
'''

multiple = [1, 3, 5, 7, 7, 7, 8, 11, 12]
print(recursive_binary_search(7, multiple))

'''
Hmm...
Looks like we got the index 4, which is correct, but what if we wanted to find the first occurrence of an element, rather than just any occurrence?
Write a new function: find_first() that uses binary_search as a starting point.
Hint: You shouldn't need to modify binary_search() at all.
'''

def find_first(target, source):
    i = recursive_binary_search(target, source)
    if not i:
        return None
    while source[i] == target:
        if i == 0:
            return 0
        if source[i - 1] == target:
            i -= 1
        else:
            return i

multiple = [1, 3, 5, 7, 7, 7, 8, 11, 12, 13, 14, 15]
answers = [find_first(7, multiple), find_first(9, multiple)]
for answer in answers:
    if answer == 3:
        print('Pass!')
    else:
        print('Fail!')
# print(find_first(7, multiple)) # Should return 3
# print(find_first(9, multiple)) # Should return None