Binary Search in Python: An Introduction

Binary search is a fundamental algorithm in computer science. It allows for efficient searching in a sorted collection of elements. In this article, we will walk through the logic of binary search and implement it in Python.

Understanding Binary Search

Binary search works by repeatedly dividing the search space in half. If the search key is equal to the middle item of the array, then the search is successful and the position is returned. If the search key is less than the middle item, the algorithm repeats its action on the left half of the array; if the search key is greater, the algorithm repeats on the right half.

This process continues until the size of the search space is reduced to zero, which means the search key is not present in the array.

Implementing Binary Search in Python

Here's a simple implementation of binary search in Python:

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

    while low <= high:

        mid = (high + low) // 2

        if arr[mid] < x:
            low = mid + 1

        elif arr[mid] > x:
            high = mid - 1

        else:
            return mid

    return -1

This function takes a sorted list arr and a search key x. It returns the index of x if it is present in arr, and -1 otherwise.

You can use this function to search for an item in a list like this:

arr = [2, 3, 4, 10, 40]
x = 10

result = binary_search(arr, x)

if result != -1:
    print("Element is present at index", str(result))
else:
    print("Element is not present in array")

In this example, the output will be Element is present at index 3, because the number 10 is at index 3 in the array.

Wrapping Up

Binary search is an efficient algorithm for finding an item in a sorted list. It has a time complexity of O(log n), making it much faster than simple linear search methods for large datasets. By understanding and implementing binary search, you're mastering one of the fundamental algorithms in computer science.

As you continue learning and mastering algorithms, I highly recommend leveraging resources like neetcode.io. The way the content is structured and presented makes complex algorithms easy to understand.

Remember, the best way to truly understand an algorithm is to implement it yourself. After you learn an algorithm try implementing it into one of your projects instead of just moving onto the next algorithm to help solidfy what you learned.