18.6 Binary Search

Let’s first talk about the search you already know: Linear Search. This searches through everything by ascending index.

If there are a lot of things, say 10 quadrillion items, this will take 10 quadrillion searches. But Binary Search does that in log₂(10,000,000,000,000,000) which is approximately 53 steps. WOW! So this binary search just took a few trillion times fewer steps than Linear Search in this specific case.

Let’s see how it does that:

https://www.youtube.com/watch?v=jDyKUXJeCwY

As you see in the video, the one downside of binary search is that the array of things being searched must be sorted. Now, you must be thinking to yourself “doesn’t sorting take super long?”. Yes, it does, but if you were to constantly look for something, it is faster to sort it and then constantly look for that something.

Code and Breakdown:


# Code for binary search


def binary_search(arr, low, high, x):
    """
    Parameters:
    1)arr is the sorted array in which we will be finding the element
    2)low is the lower bound of the interval in which we will
    be finding the element index
    3)high is the upper bound of the interval in which we will
    be finding the element index
    4)x is the element we are trying to find the index of
    Output: the index of the element x in the array arr.
    If the element x does not exist in array arr, -1 will
    be returned.
    """

    while high >= low:
        mid = (high + low) // 2
        if arr[mid] == x:  # Base Case 1
            return mid
        elif arr[mid] < x:  # Recursive Case 1
            return binary_search(arr, mid + 1, high, x)
        else:  # Recursive Case 2
            return binary_search(arr, low, mid - 1, x)
    else:  # Base Case 2: element not found
        return -1


print(binary_search([1, 24, 28, 30, 40, 52], 0, 5, 28))

View code on GitHub.

In the code above we pass in all parameters needed: the sorted array, lowest index value, highest index value, and random value x (the user may want to search a specific range rather than the whole thing). In order to make this recursion method work, we must make it run indefinitely until it finds the index of the value or fails to. We use the condition high >= low to set the indefinite loop. Next, is the searching process in which we define 4 cases. Firstly, our best case would be that the middle term just so happened to be the number we are looking for thus ending the recursion right there. We then have two other checks, one to see whether or not the value at the middle index is greater than x, and another to check if the value is less than x. We then either divide the array in half to the right or to the left. This process continues until it either finds the index of the number or fails to do so, which would result in the function returning -1.

Previous Section

5️⃣

18.5 Iterative Fibonacci

Next Section

7️⃣

18.7 Practice

⚖️

Copyright © 2021 Code 4 Tomorrow. All rights reserved. The code in this course is licensed under the MIT License. If you would like to use content from any of our courses, you must obtain our explicit written permission and provide credit. Please contact classes@code4tomorrow.org for inquiries.