In our daily lives, we’re constantly searching for information or trying to find solutions to problems we encounter. Whether it’s browsing the web, looking up a contact in our phone, or finding the shortest route on a map, search is an integral part of our routines. Behind the scenes, various algorithms power these search processes, allowing programs to run more efficiently and deal with data more effectively.
One such algorithm is binary search. It’s a fundamental technique for efficiently finding elements in a sorted collection (such as an array or list). In this article, we’ll explore binary search in Python, understand how it works, and discuss its advantages and use cases.
Table of Contents:
Benefits of Binary Search
Overview of Binary Search Algorithm
Recursive Binary Search
Iterative Binary Search
Conclusion
What is Binary Search?
Binary search is an efficient algorithm for locating an item within a sorted list of items. It takes advantage of the fact that the array (or list) is already sorted, allowing it to reduce the search space by half with each step. The key idea is to repeatedly divide the search interval in half, making it significantly faster than linear search, especially for long lists.
Benefits of Binary Search:
Efficiency: Binary search has a time complexity of O(log n), where n is the size of the array. This makes it much faster than linear search, which has a linear time complexity.
Space Complexity: Binary search requires minimal auxiliary space. In the iterative version, it uses only a few variables, and in the recursive version, the call stack depth is limited.
Sorted Data Requirement: Binary search works only on sorted data. If the data is not sorted, you’ll need to sort it first.
Overview of Binary Search Algorithm
Below is the pseudocode for implementing binary search in Python. This algorithm is used to find a specific value in a sorted list or array efficiently:
# Binary Search Pseudocode
function binary_search(arr, low, high, x):
if low >= high:
# Base case: Element not found
return -1
mid = (low + high) // 2
if arr[mid] == x:
# Element found at index 'mid'
return mid
elif arr[mid] < x:
# Search the right half
return binary_search(arr, mid + 1, high, x)
else:
# Search the left half
return binary_search(arr, low, mid - 1, x)Let’s illustrate binary search with an example. Consider the sorted array:
arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]Suppose we want to find the target value 23.
Calculate the middle index: (low + high) // 2 = 5.
Compare the middle element (16) with the target (23).
Since 23 is greater than 16, move the search space to the right half.
Repeat the process with the new search space [23, 38, 56, 72, 91].
Calculate the new middle index: (low + high) // 2 = 8.
Compare the middle element (56) with the target (23).
Since 23 is less than 56, move the search space to the left half.
Continue until the target is found (index 5).
Click here to learn the Binary Search Algorithm in detail: Binary Search Algorithm
Implementing Binary Search in Python
You can implement binary search in Python using either the recursive or iterative approach.
Recursive Binary Search:
Recursive binary search is an algorithm used to find a specific value in a sorted list or array. It efficiently narrows down the search space by dividing it in half with each comparison. The key idea is to recursively divide the search interval until the target value is found or the entire search space is exhausted.
Recursive binary search significantly reduces the search space with each step, making it faster than linear search.
Example 1: Find the index of a number
Let’s create our own sorted list and search for a target value. Suppose arr = [10, 20, 30, 40, 50, 60, 70] and we want to find 40.
def binary_search(arr, low, high, x):
if high >= low:
mid = (high + low) // 2
if arr[mid] == x:
return mid
elif arr[mid] > x:
return binary_search(arr, low, mid - 1, x)
else:
return binary_search(arr, mid + 1, high, x)
else:
return -1
arr = [10, 20, 30, 40, 50, 60, 70]
x = 40
result = binary_search(arr, 0, len(arr) - 1, x)
if result != -1:
print("Element is present at index", result)
else:
print("Element is not present in the array")Example 2: Target Not Found
Let’s search for a value that is not in the list. Suppose arr = [1, 3, 5, 7, 9] and we want to find 4.
def binary_search(arr, low, high, x):
if high >= low:
mid = (high + low) // 2
if arr[mid] == x:
return mid
elif arr[mid] > x:
return binary_search(arr, low, mid - 1, x)
else:
return binary_search(arr, mid + 1, high, x)
else:
return -1
arr = [1, 3, 5, 7, 9]
x = 4
result = binary_search(arr, 0, len(arr) - 1, x)
if result != -1:
print("Element is present at index", result)
else:
print("Element is not present in the array")Time Complexity:
Binary search divides the search space in half at each step.
The time complexity is O(log n), where n is the size of the array.
This efficiency makes binary search significantly faster than linear search.
Auxiliary Space:
The auxiliary space (memory used by the call stack) is also O(log n) due to recursion.
Each recursive call creates a new stack frame.
However, this space is minimal compared to linear search.
Iterative Binary Search:
Iterative binary search is an algorithm used to find a specific value in a sorted list or array. Unlike the recursive version, it uses a loop to repeatedly narrow down the search space by dividing it in half. The key idea remains the same: efficiently locate the target value.
Example:
Suppose we have a sorted list arr = [2, 3, 4, 10, 40], and we want to find the index of the target value 10 using iterative binary search.
def binary_search(arr, x):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == x:
return mid
elif arr[mid] < x:
low = mid + 1
else:
high = mid - 1
return -1
arr = [2, 3, 4, 10, 40]
x = 10
result = binary_search(arr, x)
if result != -1:
print("Element is present at index", result)
else:
print("Element is not present in the array")Space Efficiency:
The iterative binary search has a space complexity of O(1).
It uses only a few variables (no additional memory allocation).
Unlike the recursive version, it does not create a call stack.
Perform Binary Search in Python with bisect Module
The bisect module in Python provides efficient tools for maintaining a list in sorted order without having to sort the list after each insertion. It is built upon the binary search algorithm and offers functions that abstract the complexity of bisection, making it easy to integrate into your code.
Algorithm
Here is the algorithm for performing binary search using Python's bisect module:
Initialize Pointers: Set low to 0 and high to the last index of the sorted list.
Loop:
Calculate the mid index as (low + high) // 2.
Compare the element at mid with the target value.
If equal, return the index.
Otherwise, adjust the pointers (low or high) based on the comparison.
Repeat until low is less than or equal to high.
Pseudocode:
# Binary Search Using bisect Module
def binary_search(arr, x):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == x:
return mid
elif arr[mid] < x:
low = mid + 1
else:
high = mid - 1
return -1Example 1. Finding the First Occurrence of an Element
The bisect.bisect_left(a, x, lo=0, hi=len(a)) function returns the leftmost insertion point of x in a sorted list a. If x is already present in a, the insertion point will be before (to the left of) any existing entries.
Here’s an example:
from bisect import bisect_left
def binary_search(a, x):
i = bisect_left(a, x)
if i != len(a) and a[i] == x:
return i
else:
return -1
a = [1, 2, 4, 4, 8]
x = 4
res = binary_search(a, x)
if res != -1:
print(f"First occurrence of {x} is present at index {res}")
else:
print(f"{x} is absent")Example 2. Finding Greatest Value Smaller Than x
The bisect.bisect_left(a, x) function can also be used to find the largest value smaller than x:
def binary_search(a, x):
i = bisect_left(a, x)
if i:
return i - 1
else:
return -1
a = [1, 2, 4, 4, 8]
x = 7
res = binary_search(a, x)
if res != -1:
print(f"Largest value smaller than {x} is at index {res}")
else:
print(f"No value smaller than {x}")Example 3. Finding Rightmost Occurrence
To find the rightmost occurrence of an element, you can use bisect.bisect_right(a, x):
def binary_search(a, x):
i = bisect_right(a, x)
if i != 0 and a[i - 1] == x:
return i - 1
else:
return -1
a = [1, 2, 4, 4]
x = 4
res = binary_search(a, x)
if res != -1:
print(f"Last occurrence of {x} is present at index {res}")
else:
print(f"{x} is absent")
Advantages and Use Cases
Efficiency: The bisection algorithm’s logarithmic time complexity makes it highly efficient for searching in large sorted sequences.
Ease of Use: The bisect module provides simple functions that abstract the complexity of the bisection algorithm, making it easy to integrate into your code.
Conclusion:
In short:
Binary search is an efficient algorithm for finding elements in a sorted list.
It works by dividing the search space in half with each comparison.
Recursive and iterative implementations are available.
Python’s bisect module provides useful tools for binary search.
Komentáře