<jupyter_start><jupyter_text>Variations on Binary Search Now that you've gone through the work of building a binary search function, let's take some time to try out a few exercises that are variations (or extensions) of binary search. We'll provide the function for you to start:<jupyter_code>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 + left
    elif source[center] < target:
        return recursive_binary_search(target, source[center+1:], left+center+1)
    else:
        return recursive_binary_search(target, source[:center], left)<jupyter_output><empty_output><jupyter_text>Find FirstThe 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:<jupyter_code>multiple = [1, 3, 5, 7, 7, 7, 8, 11, 12]
recursive_binary_search(7, multiple)<jupyter_output><empty_output><jupyter_text>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.<jupyter_code>def find_first(target, source):
    idx = recursive_binary_search(target, source)
    if idx is None:
        return None
    while source[idx] == target:
        if idx == 0:
            return 0
        if source[idx-1] == target:
            idx -= 1
        else:
            return idx

multiple = [1, 3, 5, 7, 7, 7, 8, 11, 12, 13, 14, 15]
print(find_first(7, multiple)) # Should return 3
print(find_first(9, multiple)) # Should return None


## Add your own tests to verify that your code works!<jupyter_output>3
None<jupyter_text>Spoiler - Solution below:Here's what we came up with! You're answer might be a little different.```pythondef find_first(target, source):    index = recursive_binary_search(target, source)    if not index:        return None    while source[index] == target:        if index == 0:            return 0        if source[index-1] == target:            index -= 1        else:            return index```<jupyter_code>def find_first(target, source):
    index = recursive_binary_search(target, source)
    if not index:
        return None
    while source[index] == target:
        if index == 0:
            return 0
        if source[index-1] == target:
            index -= 1
        else:
            return index

multiple = [1, 3, 5, 7, 7, 7, 8, 11, 12, 13, 14, 15]
print(find_first(7, multiple)) # Should return 3
print(find_first(9, multiple)) # Should return None<jupyter_output>3
None<jupyter_text>ContainsThe second variation is a function that returns a boolean value indicating whether an element is _present_, but with no information about the location of that element.For example:```pythonletters = ['a', 'c', 'd', 'f', 'g']print(contains('a', letters))  Trueprint(contains('b', letters))  False```There are a few different ways to approach this, so try it out, and we'll share two solutions after.<jupyter_code>def contains(target, source):
    index = recursive_binary_search(target, source)
    if index is not None:
        return True
    else:
        return False

letters = ['a', 'c', 'd', 'f', 'g']
print(contains('a', letters)) ## True
print(contains('b', letters)) ## False<jupyter_output>True
False<jupyter_text>Spoiler - Solution below:Here are two solutions we came up with:One option is just to wrap binary search:```pythondef contains(target, source):    return recursive_binary_search(target, source) is not None```Another choice is to build a simpler binary search directly into the function:```pythondef contains(target, source):     Since we don't need to keep track of the index, we can remove the `left` parameter.    if len(source) == 0:        return False    center = (len(source)-1) // 2    if source[center] == target:        return True    elif source[center] < target:        return contains(target, source[center+1:])    else:        return contains(target, source[:center])```Try these functions out below:<jupyter_code># Loose wrapper for recursive binary search, returning True if the index is found and False if not
def contains(target, source):
    return recursive_binary_search(target, source) is not None

letters = ['a', 'c', 'd', 'f', 'g']
print(contains('a', letters)) ## True
print(contains('b', letters)) ## False


# Native implementation of binary search in the `contains` function.
def contains(target, source):
    if len(source) == 0:
        return False
    center = (len(source)-1) // 2
    if source[center] == target:
        return True
    elif source[center] < target:
        return contains(target, source[center+1:])
    else:
        return contains(target, source[:center])

letters = ['a', 'c', 'd', 'f', 'g']
print(contains('c', letters)) ## True
print(contains('b', letters)) ## False<jupyter_output>True
False
{'fraction_non_alphanumeric': 0.11197663096397274, 'fraction_numerical': 0.018111002921129504, 'mean_word_length': 3.7555555555555555, 'pattern_counts': {'":': 0, '<': 24, '<?xml version=': 0, '>': 22, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '34673', 'license': 'MIT', 'n_tokens_mistral': 1588, 'n_tokens_neox': 1471, 'n_words': 572, 'path': 'Basic Algorithms/Basic Algorithms/binary_search_variations.ipynb', 'repo_name': 'gmendozah/Data-Structures-and-Algorithms', 'size': '5135'}