Binary Search Explained

Welcome to this tutorial on binary search, a fundamental algorithm in computer science. Binary search is an efficient way to find an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you’ve narrowed the possible locations to just one. In this tutorial, we will explore how binary search works, its advantages, and how to implement it in code.

What is Binary Search?

Binary search is a fast search algorithm that finds the position of a target value within a sorted array. It compares the target value to the middle element of the array and eliminates half of the array during each iteration until the target value is found. This algorithm is much faster than a linear search, especially for large datasets.

# Example of a sorted list
sorted_list = [1, 2, 3, 4, 5, 6, 7, 8, 9]

How Binary Search Works

The binary search algorithm works by following these steps: start with a sorted list, find the middle element, compare the middle element to the target value, eliminate half of the list based on the comparison, and repeat the process until the target value is found. If the target value is not found after the list has been fully traversed, the algorithm returns a “not found” result.

def binary_search(sorted_list, target):
    low = 0
    high = len(sorted_list) - 1
    while low <= high:
        mid = (low + high) // 2
        if sorted_list[mid] == target:
            return mid
        elif sorted_list[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1  # not found

Time Complexity of Binary Search

The time complexity of binary search is O(log n), where n is the number of items in the list. This is because with each iteration, the algorithm eliminates half of the list, resulting in a logarithmic number of steps to find the target value. This makes binary search much faster than linear search, which has a time complexity of O(n), especially for large datasets.

import time
import random

# Generate a large sorted list
large_list = sorted([random.randint(0, 10000) for _ in range(10000)])

# Measure the time it takes to find an item using binary search
start_time = time.time()
index = binary_search(large_list, 5000)
end_time = time.time()
print(f"Binary search took {end_time - start_time} seconds")

Space Complexity of Binary Search

The space complexity of binary search is O(1), which means it uses a constant amount of space. This is because the algorithm only needs to keep track of a few variables, such as the low and high indices, and the target value, regardless of the size of the input list.

def binary_search_inplace(sorted_list, target):
    low = 0
    high = len(sorted_list) - 1
    while low <= high:
        mid = (low + high) // 2
        if sorted_list[mid] == target:
            return mid
        elif sorted_list[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1  # not found

Real-World Applications of Binary Search

Binary search has many real-world applications, such as searching for a word in a dictionary, finding a specific record in a database, or locating a specific file on a computer. It is also used in many algorithms, such as sorting algorithms and graph algorithms.

# Example of using binary search to find a word in a dictionary
dictionary = ["apple", "banana", "cherry", "date", "elderberry"]
target_word = "cherry"
index = binary_search(dictionary, target_word)
if index != -1:
    print(f"The word '{target_word}' is at index {index}")
else:
    print(f"The word '{target_word}' is not in the dictionary")

Conclusion

In conclusion, binary search is a fast and efficient algorithm for finding an item in a sorted list. Its time complexity of O(log n) makes it much faster than linear search, especially for large datasets. The space complexity of O(1) means it uses a constant amount of space, making it suitable for use in a wide range of applications. By understanding how binary search works and how to implement it in code, you can write more efficient and effective algorithms for searching and sorting data.