Binary search is an efficient algorithm for finding an element in a sorted array. It works by repeatedly dividing the search interval in half, eliminating parts of the array that cannot contain the target element until it is found. Binary search is much faster than linear search, especially for large arrays, as it eliminates half of the remaining elements after each iteration. This article provides a comprehensive guide on implementing binary search in Python, examining the algorithm logic, code examples, complexity analysis, and variations.
Table of Contents
Open Table of Contents
Overview of Binary Search
Binary search follows the divide-and-conquer algorithm strategy to search for an element in an array. The key requirements are:
-
The array must be sorted in ascending or descending order. This allows comparing the target value to the middle element to determine which half of the array to search next.
-
The array indices, starting position, ending position, and middle index must be tracked to determine the current search interval.
The basic steps are:
-
Initialize the start and end index for the search space.
-
Calculate the middle index as the average of the start and end indices.
-
Compare the target value to the middle element.
-
If it matches, return the middle index.
-
Else if the target is less than the middle, make the end index equal to the middle - 1.
-
Else if the target is greater than the middle, make the start index equal to the middle + 1.
-
Repeat steps 2-6, successively narrowing the search space interval, until the target is found or the interval is empty.
-
If the search space empties, return -1 to indicate the target is not found.
This halves the search space each iteration, providing a worst-case time complexity of O(log n).
Python Implementation of Binary Search
Here is an implementation of binary search in Python:
def binary_search(arr, target):
start = 0
end = len(arr) - 1
while start <= end:
mid = (start + end) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
start = mid + 1
else:
end = mid - 1
return -1
-
It takes the sorted array
arr
and target elementtarget
as parameters. -
Two indices
start
andend
track the search space. -
The
while
loop runs till the start index is less than or equal to the end. -
The mid index is calculated as the average of the start and end indices.
-
The target is compared to the middle element. If equal, the mid index is returned.
-
Otherwise, the start or end is adjusted to narrow the search space.
-
After the loop, -1 is returned if the target is not found.
To use this function:
arr = [1,5,23,111,144,500]
target = 144
result = binary_search(arr, target)
if result != -1:
print("Element found at index", result)
else:
print("Element not found")
This prints “Element found at index 4”, since 144 exists at index 4 in the array.
Handling Edge Cases
The basic implementation above does not handle edge cases properly. Here are some improvements:
1. Empty array: Check if the array is empty before searching and return -1 directly.
if len(arr) == 0:
return -1
2. Out of bounds indices: Calculate the mid index using:
mid = start + (end - start) // 2
This avoids overflow when start and end are large.
3. Repeated elements: Return the leftmost index in case of duplicates.
while start < end:
# Other code
if arr[mid] == target:
end = mid
return start
Complexity Analysis
Time Complexity:
As the search space is halved each iteration, binary search takes O(log n) time in the worst case, where n is the array size. The number of iterations before the space is reduced to 1 is log2(n).
Space Complexity:
The algorithm runs in O(1) constant space, as it only stores the start, end, mid indices and does not use any other data structure.
Optimizations and Variations
Here are some optimizations and variations of binary search:
-
Iterative vs Recursive: The iterative approach above uses a loop. Recursive binary search recursively calls itself on the first or second half of the array.
-
Search Space Reduction: If the search space can be reduced beyond half based on additional checks, the search can converge faster.
-
Index of First Occurrence: Track the first index matching the target for duplicate elements.
-
Binary Search on Strings: Apply binary search on a lexicographically sorted array of strings.
-
Binary Search on Rotated Array: Search a rotated sorted array efficiently by determining which half is sorted.
-
Ternary Search: Use three indices to divide array into thirds for faster convergence.
-
Exponential Search: Perform binary search after using exponential search for search space reduction.
-
Interpolation Search: Use a probe index calculated from the key value for faster search.
Example Binary Search Code Snippets
Here are some examples demonstrating the optimizations and variations of binary search discussed above:
Recursive Implementation
def binary_search_recursive(arr, target, start, end):
if start > end:
return -1
mid = (start + end) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search_recursive(arr, target, mid+1, end)
else:
return binary_search_recursive(arr, target, start, mid-1)
# Initial call
result = binary_search_recursive(arr, target, 0, len(arr)-1)
Search First Occurrence
def binary_search_first(arr, target):
start = 0
end = len(arr) - 1
first_index = -1
while start <= end:
mid = (start + end) // 2
if arr[mid] == target:
first_index = mid
end = mid - 1
elif arr[mid] < target:
start = mid + 1
else:
end = mid - 1
return first_index
Binary Search on String Array
strings = ["apple", "mango", "orange", "pear"]
target = "mango"
# Lexicographically sort strings
strings.sort()
def binary_search_string(strings, target):
# Implement string binary search
print(binary_search_string(strings, target))
Search Rotated Sorted Array
def search_rotated_array(arr, target):
pivot = find_pivot(arr)
# Search in first half
if arr[pivot] <= target <= arr[len(arr)-1]:
return binary_search(arr, target, 0, pivot)
# Search in second half
else:
return binary_search(arr, target, pivot+1, len(arr)-1)
def find_pivot(arr):
start = 0
end = len(arr) - 1
while start <= end:
mid = (start + end) // 2
if mid < end and arr[mid] > arr[mid + 1]:
return mid
elif mid > start and arr[mid] < arr[mid - 1]:
return mid-1
elif arr[start] >= arr[mid]:
end = mid - 1
else:
start = mid + 1
These demonstrate how binary search can be adapted to different scenarios and use cases. The key ideas remain dividing the search space and progressively narrowing intervals.
Applications of Binary Search
Binary search is used extensively in various domains:
Searching Sorted Data: Arrays, lists, matrices, databases, files
Optimization Algorithms: Minimum/maximum finding, Golden section search
Resource Locations: Jump tables, memory addresses, pages, blocks, sectors
Data Compression: Dictionary-based like LZW, predictive coding
Signal Processing: Noise thresholding, step detection, pulse detection
Networking: MAC forwarding table lookups, IP lookups, port lookups
Graphics: Lighting calculation, anti-aliasing, ray tracing
Physics and Mathematics: Root finding, inequality solving, simulations
Games: Movement optimizations, pathfinding, terrain generation
Distributed Systems: Lookup services, source coding, redundancy removal
Machine Learning: Hyperparameter optimization, neural architecture search, clustering
Cryptography: Ciphertext searching, collision finding, identity testing
Bioinformatics: Genome alignment, protein sequencing, BLAST search
As a powerful algorithm at the core of computing, binary search enables efficiencies in virtually every technical field. Mastering implementations in Python is key for computer science and coding interviews.
Conclusion
Binary search is a fundamental algorithm that greatly speeds up searching in sorted arrays. This guide covered how it works, Python implementations, edge cases, optimizations, variations, code examples, complexity analysis, and applications. The key ideas are utilizing the sorted order to eliminate halves of the search space each iteration and recursively narrowing the interval till the target is found. With practice, binary search can be adapted to various use cases. Fluency in binary search coding questions demonstrates strong technical and analytical skills crucial for programming interviews and roles.