Mastering the Art of Binary Search
Binary search is a fundamental algorithm that every programmer should master. Not only is it incredibly efficient for searching sorted arrays, but it also forms the basis for many advanced problem-solving techniques. In this blog post, we'll explore various binary search patterns that frequently appear in coding interviews.
The Classic Binary Search
Let's start with the classic implementation:
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
This algorithm works on a sorted array by repeatedly dividing the search interval in half:
[ 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 ]
^ ^ ^
left mid right
Finding the Leftmost Occurrence
A common variation is finding the leftmost occurrence of a target value:
def leftmost_binary_search(arr, target):
left, right = 0, len(arr) - 1
result = -1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
result = mid
right = mid - 1 # Continue searching left
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return result
This is useful for arrays with duplicates:
[ 1 | 2 | 2 | 2 | 3 | 4 | 4 | 5 ]
^ ^ ^
| | rightmost
| mid
leftmost
Binary Search on Answer
Sometimes, we use binary search to find an optimal value that satisfies a condition:
def binary_search_on_answer(condition):
left, right = 0, 10**9 # Adjust range as needed
while left < right:
mid = left + (right - left) // 2
if condition(mid):
right = mid
else:
left = mid + 1
return left
This pattern is often used in problems like "find the minimum time to complete a task" or "find the maximum value that satisfies a constraint".
Binary Search on Rotated Sorted Array
A tricky variation is searching in a rotated sorted array:
def search_rotated(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
# Check which half is sorted
if arr[left] <= arr[mid]:
if arr[left] <= target < arr[mid]:
right = mid - 1
else:
left = mid + 1
else:
if arr[mid] < target <= arr[right]:
left = mid + 1
else:
right = mid - 1
return -1
This works on arrays like:
[ 4 | 5 | 6 | 7 | 0 | 1 | 2 ]
^ ^ ^
left mid right
Binary Search on 2D Matrix
Binary search can be extended to 2D matrices:
def search_matrix(matrix, target):
if not matrix or not matrix[0]:
return False
rows, cols = len(matrix), len(matrix[0])
left, right = 0, rows * cols - 1
while left <= right:
mid = left + (right - left) // 2
mid_value = matrix[mid // cols][mid % cols]
if mid_value == target:
return True
elif mid_value < target:
left = mid + 1
else:
right = mid - 1
return False
This treats the 2D matrix as a flattened sorted array:
[ 1 | 3 | 5 ]
[ 7 | 9 | 11 ]
[ 13 | 15 | 17 ]
Flattened:
[ 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 ]
Conclusion
These patterns cover a wide range of binary search applications you might encounter in coding interviews. Remember, the key to mastering binary search is understanding the core concept of narrowing down the search space efficiently. Practice these patterns, and you'll be well-prepared for any binary search challenge that comes your way!