Binary search in Python 101: Implementation and use cases

https://roadmap.sh/python/binary-search • 159 KB fetched
Open original page
Binary search in Python 101: Implementation and use cases AI Tutor
*
Roadmaps
* AI Tutor
Lesson Packs Newsletters

Loading...

Binary search in Python 101: Implementation and use cases
William Imoh Prefer us on Google
The difference between a slow search and a fast one often comes down to the algorithm you choose. A good search algorithm , e.g., binary search, helps you to find data faster without having to scan the entire list. Binary search is a fundamental search algorithm in computer science that minimizes the number of comparisons required to find a target. Understanding this search algorithm helps Python developers work better with sorted data structures.
Python allows you to implement binary search in various ways. It lets you write your own binary search using loops or recursion . If you prefer not to write it yourself, Python includes built-in functions, like the bisect module , that handle it for you. Whether you write it yourself or use a built-in function, binary search needs a sorted list. When you sort your data, searches are faster, and knowing which method to use matters.
In this Article
* What is binary search in Python?

* Binary search vs. linear search algorithm

* Implementation of binary search in Python

* Understanding space and time complexity

* Practical applications of binary search

* Common errors and best practices

* Wrapping up

*

Knowing how to search sorted lists is a skill that rewards you throughout your career as a developer. It improves how you think about speed and problem-solving when writing code. Learning binary search also prepares you for technical job interviews. Interviewers use binary search questions to assess your coding and problem-solving skills.
In this guide, you'll learn everything you need to know about binary search in Python. You’ll then see how to implement it in Python and when to use it. For a detailed view of Python basics and algorithms to learn, check out the Python roadmap .
What is binary search in Python?
Binary search in Python is an efficient searching algorithm that finds the index of a target value in a sorted array or list. It uses a divide-and-conquer approach to search for a specific element in a list. By dividing the search interval in half at each step, it runs much faster than checking every element one by one.
Binary search works by first checking the middle element in your sorted list. If the middle element matches your target value, the search is complete. If your target value is smaller than the middle element, the search will proceed in the left half. But if the target value is greater, the search algorithm will ignore the left half and search the right half. This process will continue until you find your target value or run out of elements to check.
To better understand how binary search works, here is an example of finding the target number 13:
python

numbers = [2, 5, 8, 12, 13, 17, 20, 23, 26]  target = 13 # Indices: 0 1 2 3 4 5 6 7 8

The sorted array in the above example, [2, 5, 8, 12, 13, 17, 20, 23, 26], has 9 elements, with indices ranging from 0 to 8. The binary search algorithm will follow these steps:

* Step 1 : Check the element at the middle index (4), which has a value of (13). Since it matches the target value (13) you’re looking for, the search stops. The search algorithm will then return index (4) as the target value index.

Using the same sorted array, let’s look for 17 in a search where the target value is not in the middle index:

* Step 1 : The middle index is 4 with a middle value of 13. Since 17 > 13, the binary search algorithm will ignore the left half (indices 0-4: 2, 5, 8, 12, 13). But it’ll continue searching the right half.

* Step 2 : In the remaining sorted array [17, 20, 23, 26], the new middle index is 6 with a middle value of 20. Since 17 < 20, the binary search algorithm will ignore the right side and keep the left.

* Step 3 : At this point, only [17] remains in your sorted array. The binary search algorithm will then return index 5 as the target value index.

Binary search requires direct access to elements by their index. It does not work well with data structures like linked lists because they do not support direct access to any position. You must process each node one by one, which cancels out the speed advantage of binary search.
Remember to sort your data in either ascending or descending order before applying binary search. If you skip this step and run binary search on unsorted data, the algorithm will fail. It might yield incorrect results or skip your target value entirely.
In the example above, binary search found the target value in just three comparisons out of nine elements because you sorted your data. Without sorting, you would need to use other search algorithms, such as linear search, which may require up to nine checks to find the target value.
Binary search vs. linear search algorithm
Binary search is effective, but not always the best choice. In some situations, a simpler method such as a linear search algorithm is more suitable. Knowing both algorithms will help you choose the right one for your projects.
The linear search algorithm uses a straightforward approach to finding elements in a list or array. It goes through the list step by step until you find your desired value or reach the last element. This one-by-one approach works, but it can be slow when you have lots of data to search through.
The linear search algorithm can only eliminate one element at a time. If the first element matches your target value, the search is complete. But if it's at the end or not in the list at all, the linear search algorithm must check every element. The algorithm reduces the search space by exactly one each time it checks an element against the target value.
You can use linear search on unsorted data, unlike binary search, which requires the data to be sorted. It involves scanning a list in any order and comparing each value to the target value from left to right. The linear search algorithm is a good choice for small lists and for data structures like linked lists that don't support direct access to the middle element. It also works well when you only need to search once or when you need to find all matching values.
AI Tutor
Explain the linear search algorithm with a simple visual example.

In contrast, binary search eliminates half of the remaining elements with every comparison. Instead of checking elements one by one, it halves the search space over and over again. Use binary search when working with sorted data structures. It's well-suited for large lists, repeated searches, and cases where speed is important.
The way linear and binary search reduce the search space affects how fast they run. Big O notation helps explain how a program's runtime changes as input size increases. With Big O notation , you predict whether your search will take 30 steps or 30,000 steps based on how much data you have.
Besides binary and linear search, you can also use hash-based search to find data. Hash functions map data directly to specific locations in a hash table, making lookups faster if you do not need the data to remain sorted. Hash table lookups have an average O(1) time complexity, making them even faster than binary search's O(log n) for direct key access. Binary search works better with sorted data and supports ordered operations. The right method depends on how your data is set up and what you need from your search.
AI Tutor
Explain what Big-O notation is?

Implementation of binary search in Python
Now that you know binary search and how it works, let's look at a few ways to implement binary search in Python .
Python, like any programming language, gives you flexible ways to implement binary search algorithms. It lets you pick the approach that best fits your needs, whether you want something simple, fast, or built-in. The following are the three most common methods to implement binary search:

* Recursive implementation

* Iterative binary search (using a while loop)

* Using Python's built-in bisect module

Recursive implementation of binary search
The recursive implementation of binary search follows the divide-and-conquer approach to solving problems. It divides the data, checks one half, and then applies the same logic to the remaining relevant half. The recursive method applies binary search by solving problems through repeated function calls.
At each step, a recursive call focuses on a smaller section of the sorted array or list. It reduces the search space until it finds the target value or no elements remain. This action results in a logarithmic time complexity, making searching much faster than a simple linear search as the list size grows.
However, this approach has a limitation: Every recursive call adds a new layer to the call stack. It keeps the function calls active until the search finishes. The recursive method uses more memory than the iterative approach. However, binary search needs a few steps, so the extra memory use is rarely a problem in practice. Many developers choose the iterative version for performance-critical systems to avoid additional memory usage.
python

def binary_search_recursive(arr, target, left=0, right=None):     if right is None:         right = len(arr) - 1     if left > right:         return -1     mid = (left + right) // 2     if arr[mid] == target:         return mid     elif arr[mid] < target:         return binary_search_recursive(arr, target, mid + 1, right)     else:         return binary_search_recursive(arr, target, left, mid - 1) numbers = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20] result = binary_search_recursive(numbers, 8) print(f"Found at index: {result}")  # Output: Found at index: 3

The recursive binary search algorithm works as follows:

* Step 1: If right is not provided (i.e., it is None), set it to the last index to define the whole search space.

* Step 2 : If left is greater than right, the search space is empty. The function returns -1 to show the target element is not present.

* Step 3 : Find the middle index using the floor division operator (//): mid = (left + right) // 2. For example, (0 + 9) // 2 equals 4.

* Step 4 : Compare the middle element to the target. If they do not match, the algorithm continues searching. In your example, the value at index 4 is 10, but you're looking for 8, so it doesn't match. The binary search algorithm will keep searching since it cannot return an index yet.

* Step 5 : If the middle value is less than the target number, search the right half starting at mid + 1. If it is greater, search the left half ending at mid - 1.

* Step 6 : The function returns the index of the target element when successful, or -1 when the search fails, and passes the result to any pending recursive calls.

Note : The // operator divides two numbers without keeping the remainder. For example, (0 + 9) // 2 will equal 4 instead of 4.5.

AI Tutor
Can you give me a high-level explanation of recursion in Python?

Iterative binary search (using a while loop)
You should opt for the iterative method if you're looking for speed and reliability. Unlike recursion, it handles large datasets without running out of memory space . The iterative version of binary search uses a while loop rather than recursive function calls to narrow the search range. It repeats this process until it finds the target element or confirms it doesn't exist.
The iterative binary search algorithm relies on two pointers to track the limits of your search range. This makes it straightforward to follow what's happening and catch any errors. Since the algorithm runs in one loop, many beginners find iterative binary search easier to learn. It lets you track each step one at a time without having to consider how function call stacks work.
Let's implement binary search iteratively with a while loop. You'll search for 13 in this sorted list:
python

def binary_search_iterative(arr, target):     left = 0     right = len(arr) - 1          while left <= right:         mid = (left + right) // 2                  if arr[mid] == target:             return mid         elif arr[mid] < target:             left = mid + 1         else:             right = mid - 1          return -1 numbers = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19] result = binary_search_iterative(numbers, 13) print(f"Found at index: {result}")  # Output: Found at index: 6

This is how the iterative binary search algorithm works:

* Step 1 : Set the left pointer to index 0 and the right pointer to index 9 to define the search range.

* Step 2 : Run the loop while the left is less than or equal to the right pointer to make sure the search range is not empty.

* Step 3 : Find the middle index using mid = (left + right) // 2.

* Step 4 : Compare the middle element to the target element to check for a match.

* Step 5 : If the middle element is less than the target element, set the left pointer to mid + 1 to search the right half. If it is greater, set the right pointer to mid - 1 to search the left half.

* Step 6 : If the target element is not found, return -1 to show it is not in the sorted list.

Using Python's built-in bisect module
Python provides an optimized built-in bisect module for implementing binary search. It has built-in functions for binary search, so you don't have to write algorithms by yourself. The bisect module helps you locate insertion points in a sorted list. You can use it to maintain sorted data structures without re-sorting the entire list every time you add an element .
The bisect module uses C for its internal logic, making it much faster than regular Python implementations. It does not show if an element exists on its own. But you can use it to search for elements and insert them into a sorted list without slowing things down.
Let's take a look at how to use the bisect module with some practical examples.
python

import bisect numbers = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100] # Find the insertion point for your value pos = bisect.bisect_left(numbers, 40) print(f"Position: {pos}")  # Output: Position: 3 # Check if the element exists target = 40 pos = bisect.bisect_left(numbers, target) if pos < len(numbers) and numbers[pos] == target:     print(f"Found {target} at index {pos}") else:     print(f"{target} not found") # Insert while maintaining sorted order bisect.insort(numbers, 41) print(numbers)  # Output: [10, 20, 30, 40, 41, 50, 60, 70, 80, 90, 100]

The following explains how the bisect module works:

* Step 1: bisect_left(numbers, 41) tells you where to put 41 so the list stays sorted.

* Step 2: Check that pos < len(numbers) to confirm the position isn't beyond the list.

* Step 3: Look at numbers[pos] and see if they match your target number.

* Step 4: If the position is out of range or the value is different, your target number isn't in the list.

* Step 5: bisect.insort(numbers, 41) inserts the element into the correct place in a single step.

You have learned three different ways to use binary search in Python. All three work, but they vary in speed and memory usage. Understanding space and time complexity will help you choose the best option.
Understanding space and time complexity
Time complexity measures how long an algorithm takes to run as the data grows. It gives you a general idea of how well the algorithm will perform in different situations. For example, the binary search algorithm has a logarithmic time complexity of O(log n) . This means the algorithm keeps halving the search range, so it finds results sooner.
When you double your data size, it only adds one more step to the total search time. For instance, if you're searching through 1,000 items, it'll only take you around 10 steps using O(log n). You can see these 10 steps by dividing 1,000 by 2 over and over until you get to 1: 1,000, 500, 250, 125, 62, 31, 15, 7, 3, and finally 1.
Since each step halves the data, doubling your list to 2,000 items will add only one extra step, for a total of 11 steps. Binary search works well for large datasets because of its predictable, slow-scaling nature.
On the other hand, linear search has a linear time complexity of O(n). This means the algorithm checks items one by one, so the search time grows at the same rate as the list size. If you search through 1,000 items using linear search, you cannot use the halving process to reduce the number of steps to 10. The algorithm will check each item from the beginning and may need up to 1,000 steps. Because of this, linear search works best for small datasets and simple tasks.
All three Python binary search implementations share an O(log n) time complexity. The bisect module usually runs faster in real use, but its time complexity remains the same. Choose an implementation based on other factors, such as space complexity and code readability.
AI Tutor
Explain time complexity using a simple analogy and show me how binary search gets its O(log n) rating.

Space complexity is the amount of memory an algorithm requires to run. Iterative binary search does not need additional memory as the list grows. It has a constant space complexity of O(1). This means the amount of space the algorithm uses stays the same, regardless of how large the dataset becomes.
It only needs three variables (left, right, mid) to search the data regardless of input size. Whether you search 30 elements or 30,000 elements, the memory usage stays the same. This makes it a better option for large datasets, as it avoids the issues caused by excessive nesting.
In contrast, the recursive version of binary search uses more memory as the search goes deeper. It has O(log n) space complexity due to the call stack. When using recursion, each step creates a new nested call, and the computer keeps track of these to know where to return to after the current call completes.
Each time the function calls itself, it uses more memory. The deeper the recursion goes, the more memory it uses. This increasing memory usage can
Binary search in Python 101: Implementation and use cases

Links found on this page
