Back

Binary Search

Visualize binary search algorithm in a sorted array with different search modes

Array

1
0
3
1
5
2
7
3
9
4
11
5
13
6
15
7
17
8
19
9

Current Operation:

Ready to search. Enter a target value and click "Start" to begin.

Comparisons

0

Time Complexity

O(log n)

Space Complexity

O(1)

Array Size

10

Color Coding:

Found/Result
Mid (Comparing)
Left Bound
Right Bound
Discarded

Search Mode:

Target Value:

Simulation:

SlowFast
800ms

Current Array:

[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

What is Binary Search?

Binary Search is an efficient divide-and-conquer search algorithm that finds the position of a target value within a sorted array. It works by repeatedly dividing the search interval in half, eliminating half of the remaining elements at each step.

How It Works

The algorithm compares the target with the middle element of the array:

  1. Compare target with the middle element
  2. If equal, return the index (exact match mode)
  3. If target is smaller, search the left half
  4. If target is larger, search the right half
  5. Repeat until found or the search space is exhausted

Search Modes

  • Find Exact Value: Standard binary search - finds the exact target if it exists
  • Find Biggest < Target: Finds the largest element that is smaller than the target (useful for floor operations)
  • Find Smallest > Target: Finds the smallest element that is larger than the target (useful for ceiling operations)

Implementation

1. Exact Match

Standard binary search for exact value:

from typing import List

def binary_search_exact(arr: List[int], target: int) -> int:
    """
    Find exact match of target in sorted array using binary search.
    
    Args:
        arr: Sorted list of integers (ascending order).
        target: Value to search for.
    
    Returns:
        Index of target if found, -1 otherwise.
    
    Time Complexity: O(log n) where n is array length.
    Space Complexity: O(1).
    """
    left, right = 0, 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  # Not found

# Example
arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
target = 11
result = binary_search_exact(arr, target)
print(f"Found at index: {result}")  # Found at index: 4

2. Biggest Smaller Than Target

Find the largest element smaller than target:

from typing import List, Optional

def binary_search_biggest_smaller(arr: List[int], target: int) -> int:
    """
    Find the biggest element smaller than target in a sorted array.
    
    Args:
        arr: Sorted list of integers (ascending order).
        target: Value to find the biggest element smaller than.
    
    Returns:
        Index of biggest element smaller than target, or -1 if none exists.
    
    Time Complexity: O(log n) where n is array length.
    Space Complexity: O(1).
    """
    left, right = 0, len(arr) - 1
    result: Optional[int] = None
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] < target:
            result = mid  # Candidate found
            left = mid + 1  # Search right for bigger candidate
        else:
            right = mid - 1  # Search left
    
    return result if result is not None else -1

# Example
arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
target = 10
result = binary_search_biggest_smaller(arr, target)
if result != -1:
    print(f"Biggest smaller: {arr[result]} at index {result}")  # 9 at index 4
else:
    print("No element smaller than target")

3. Smallest Bigger Than Target

Find the smallest element larger than target:

from typing import List, Optional

def binary_search_smallest_bigger(arr: List[int], target: int) -> int:
    """
    Find the smallest element bigger than target in a sorted array.
    
    Args:
        arr: Sorted list of integers (ascending order).
        target: Value to find the smallest element bigger than.
    
    Returns:
        Index of smallest element bigger than target, or -1 if none exists.
    
    Time Complexity: O(log n) where n is array length.
    Space Complexity: O(1).
    """
    left, right = 0, len(arr) - 1
    result: Optional[int] = None
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] > target:
            result = mid  # Candidate found
            right = mid - 1  # Search left for smaller candidate
        else:
            left = mid + 1  # Search right
    
    return result if result is not None else -1

# Example
arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
target = 10
result = binary_search_smallest_bigger(arr, target)
if result != -1:
    print(f"Smallest bigger: {arr[result]} at index {result}")  # 11 at index 5
else:
    print("No element bigger than target")

Time & Space Complexity

Time Complexity:

  • Best/Average/Worst: O(log n) - Each step eliminates half of the remaining elements

Space Complexity: O(1) for iterative implementation (O(log n) for recursive)

Key Requirement: Binary search requires a sorted array. The array must be sorted in ascending order for the algorithm to work correctly.

Edge Cases & Important Considerations

Edge Cases

  • Empty array: All search modes return -1 (not found). The algorithm correctly handles this by checking left <= right which is false when the array is empty.
  • Single element: Works correctly - compares the single element with the target and returns the appropriate result.
  • Target not in range: If target is smaller than all elements, "biggest smaller" returns -1. If target is larger than all elements, "smallest bigger" returns -1.
  • Target at boundaries: Works correctly for targets at the first or last position of the array.

Handling Duplicates

When the array contains duplicate values, the behavior depends on the search mode:

  • Exact match: Returns the index of any occurrence of the target. The specific index returned depends on the search path and is not guaranteed to be the first or last occurrence.
  • Biggest smaller: If duplicates exist, returns the index of the last occurrence that is smaller than the target. If the target itself has duplicates, returns the index of the last element before the first occurrence of the target.
  • Smallest bigger: If duplicates exist, returns the index of the first occurrence that is bigger than the target. If the target itself has duplicates, returns the index of the first element after the last occurrence of the target.

Note: For finding the first or last occurrence of duplicates, you would need modified binary search variants that continue searching after finding a match.

Relationship to C++ STL

These search modes correspond to standard C++ STL algorithms:

  • Exact Match: Similar to std::binary_search() - returns whether the value exists, but doesn't give the position.
  • Biggest Smaller: Equivalent to std::lower_bound() - 1 or finding the last element before the insertion point. lower_bound() returns the first position where the target could be inserted while maintaining order.
  • Smallest Bigger: Equivalent to std::upper_bound() - returns the first position after the last occurrence of the target, or the first element greater than the target.

Key insight: lower_bound() and upper_bound() are fundamental building blocks for range queries, insertion points, and working with sorted containers in C++.

Real-World Applications

  • Searching in databases: fast lookup in sorted indexes
  • Finding boundaries: floor/ceiling operations, insertion points
  • Binary search trees: core algorithm for BST operations
  • Debugging: binary search in version control (git bisect)
  • Numerical methods: finding roots of equations