How to Implement Binary Search on a Sorted List in Python

etd_admin,

Searching through a list of items is one of the most common tasks in programming. If the list is unsorted, you usually have to check every element one by one, which can be slow for large datasets. But if the list is already sorted, you can take advantage of an efficient technique called binary search.

This article will explain how binary search works, show you how to implement it in Python, and provide a simple code example.

What is Binary Search?

Binary search is a divide-and-conquer algorithm. Instead of checking each element one by one, it repeatedly divides the search range in half until it finds the target value (or determines it isn’t present).

Here’s the basic idea:

  1. Start with the entire sorted list.
  2. Check the middle element.
    • If it matches the target, you’re done.
    • If the target is smaller, continue searching in the left half.
    • If the target is larger, continue searching in the right half.
  3. Repeat until you find the target or the search range is empty.

This reduces the search time complexity from O(n) (linear search) to O(log n), which is much faster for large lists.

Code Implementation in Python

Here’s a straightforward implementation:

def binary_search(sorted_list, target):
    left = 0
    right = len(sorted_list) - 1

    while left <= right:
        mid = (left + right) // 2  # Find the middle index
        guess = sorted_list[mid]

        if guess == target:
            return mid  # Target found, return its index
        elif guess < target:
            left = mid + 1  # Search in the right half
        else:
            right = mid - 1  # Search in the left half

    return -1  # Target not found

Example Usage

numbers = [1, 3, 5, 7, 9, 11, 13]

print(binary_search(numbers, 7))   # Output: 3 (index of 7 in the list)
print(binary_search(numbers, 2))   # Output: -1 (not found)

Key Takeaways

  • Binary search only works on sorted lists.
  • It cuts the search space in half at each step, making it very efficient.
  • You can implement a binary search algorithm on a sorted list in Python in just a few lines of code.

With this understanding, you can now confidently implement a binary search algorithm on a sorted list in Python and use it whenever you need quick lookups in sorted data.

Python