Minami's Bubble 🫧

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.

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!