Binary Search Algorithm in Python

Hello guys, I'm back with another one: Phone Book Binary Search With Python. Before we get started, I want to tell you what brought about this idea. A programmer friend (more of an acquaintance) shared a link on Whatsapp to Harvard's university CS50 theatrical style approach in teaching its Computer Science introduction courses online (you can check more about that here and the first use of the theatricality was an explanation of how a binary search algorithm works by using a phone book. I then thought about writing what a Binary Search algorithm is and how to implement the Phone Book search code in Python ... because why not?.

What is a Binary Search?

Binary search is a common computational search approach used in computer science to quickly search through a list for a specific value/key within a list/array of values. The concept behind it is to repeatedly divide the list in half portions that could contain the value until it's found or until the list is empty.

Programmatic Approach to Using a Binary Search.

• Start by examining the midpoint of the array

• If the midpoint matches the target value, return the matched index.

• If the midpoint is greater than the search value, examine the left half of the array.

• If the midpoint is less than the target value, examine the right half of the array.

• Repeat the process of dividing the search intervals until the target value is found or the remaining interval is empty.

The concept behind Binary Search is that each comparison allows discarding half of the remaining search space, leading to a shorter time complexity.

Code implementation.

Below is a Python example code of using a Binary Search to look through a phone book:

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2

        if arr[mid][0] == target:
            return arr[mid][1]

        elif arr[mid][0] < target:
            low = mid + 1

        else:
            high = mid - 1

    return None

# Example usage
phone_book = [('Musa', '+235-706-7890'), ('Uche', '+234-807-8901'), ('John', '+234-708-9012'), ('Funke', '+234-902-7883')]

name = 'Funke'
phone_number = binary_search(phone_book, name)

if phone_number:
    print(f"{name}'s phone number is {phone_number}.")
else:
    print(f"Sorry, {name}'s contact doesn't exist in the phone book.")

In the implementation above, the argument arr is a list of tuples representing the phone book, where the first element of each tuple is a name and the second element is a phone number. target is the name we're searching for, and we're returning the corresponding phone number if we find a match.

The binary_search function starts by initializing the low and high pointers to the beginning and end of the list, respectively. It then enters a loop that repeatedly computes the midpoint of the search interval and compares the name at the midpoint with the target name. If the midpoint name matches the target, the function returns the corresponding phone number. Otherwise, if the midpoint name is less than the target, the function sets low to the midpoint plus one to discard the lower half of the list. If the midpoint name is greater than the target, the function sets high to the midpoint minus one to discard the upper half of the list. If the loop completes without finding a match, the function returns None.

In the example usage, we define a tuple that represents a phone book, and then search for the phone number associated with the name 'Funke'. If we find a match, we print out the phone number. If we don't find a match, we print out a message saying there's no contact associated with the name.

Conclusion

In conclusion, the binary search algorithm is a powerful and efficient way to search for a specific value in a sorted list or array. With each comparison, it eliminates half of the remaining search space, leading to a time complexity of O(log n) in the worst case, where n is the size of the list or array.

In the Python implementation we just saw, we applied the binary search algorithm to search for a name in a phone book. By utilizing the binary search algorithm, we were able to search the phone book much faster and more efficiently than we would have with a linear search.

Follow me on Twitter for software tweets and other interesting things about life 👋🏿