Binary Search Variations & Edge Cases

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

def standard_binary_search(arr, target):
    """
    Standard binary search - returns ANY index containing target.
    Returns -1 if target is not found.
    
    PROBLEM: No guarantee about WHICH occurrence is returned!
    """
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if arr[mid] == target:
            return mid  # Returns immediately upon finding ANY match
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1
 
# Demonstration of the problem
arr = [1, 2, 3, 3, 3, 3, 4, 5]
target = 3
 
result = standard_binary_search(arr, target)
print(f"Array: {arr}")
print(f"Target: {target}")
print(f"Found at index: {result}")  # Could be 2, 3, 4, or 5!
print(f"First occurrence is at: 2")  # But we need THIS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

def naive_first_occurrence(arr, target):
    """
    FLAWED APPROACH: Find any match, then scan left.
    
    Time Complexity: O(log n + k) where k is the number of duplicates
    WORST CASE: O(n) when ALL elements match the target!
    
    This destroys the O(log n) guarantee that made binary search valuable!
    """
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if arr[mid] == target:
            # Found a match! But is it the first?
            # Naive solution: scan leftward
            while mid > 0 and arr[mid - 1] == target:
                mid -= 1  # O(k) additional work!
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1
 
# Worst case demonstration
arr = [5, 5, 5, 5, 5, 5, 5, 5, 5, 5]  # All same value
target = 5
 
# Standard binary search is O(log 10) = O(4) comparisons
# But then we scan ALL elements left - that's O(n) linear scan!
# Total: O(log n + n) = O(n) - we've lost all benefits!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

def leftmost_binary_search(arr: list, target: int) -> int:
    """
    Find the leftmost (first) occurrence of target in a sorted array.
    
    Returns the index of the first occurrence of target.
    Returns -1 if target is not in the array.
    
    Time Complexity: O(log n) - guaranteed, regardless of duplicates
    Space Complexity: O(1)
    
    Invariant maintained throughout:
    - All elements at indices < left are definitely < target
    - All elements at indices >= right are definitely >= target
    - Elements in [left, right) are unexplored
    """
    if not arr:  # Handle empty array edge case
        return -1
    
    left = 0
    right = len(arr)  # Note: right is exclusive (len, not len-1)
    
    # Loop until unexplored region is empty
    while left < right:
        # Compute midpoint (avoiding integer overflow)
        mid = left + (right - left) // 2
        
        if arr[mid] < target:
            # arr[mid] is in the left region (< target)
            # We can exclude it from consideration
            left = mid + 1
        else:
            # arr[mid] >= target, so it's in the right region
            # It might be the first occurrence, so don't exclude it!
            right = mid
    
    # left now points to the boundary:
    # - the first index where arr[left] >= target
    # - could be len(arr) if all elements are < target
    
    # Check if we actually found the target
    if left < len(arr) and arr[left] == target:
        return left
    else:
        return -1  # Target not found
 
 
# Comprehensive test cases
def test_leftmost_binary_search():
    # Test case 1: Multiple occurrences
    arr1 = [1, 2, 3, 3, 3, 3, 4, 5]
    assert leftmost_binary_search(arr1, 3) == 2, "Should find first 3"
    
    # Test case 2: Single occurrence
    arr2 = [1, 2, 3, 4, 5]
    assert leftmost_binary_search(arr2, 3) == 2, "Should find the only 3"
    
    # Test case 3: Target not present
    arr3 = [1, 2, 4, 5]
    assert leftmost_binary_search(arr3, 3) == -1, "3 not present"
    
    # Test case 4: All same elements
    arr4 = [3, 3, 3, 3, 3]
    assert leftmost_binary_search(arr4, 3) == 0, "First of all 3s"
    
    # Test case 5: Target at beginning
    arr5 = [1, 1, 1, 2, 3]
    assert leftmost_binary_search(arr5, 1) == 0, "First element"
    
    # Test case 6: Target at end
    arr6 = [1, 2, 3, 5, 5, 5]
    assert leftmost_binary_search(arr6, 5) == 3, "First 5"
    
    # Test case 7: Empty array
    assert leftmost_binary_search([], 3) == -1, "Empty array"
    
    # Test case 8: Single element - found
    assert leftmost_binary_search([3], 3) == 0, "Single element found"
    
    # Test case 9: Single element - not found (less)
    assert leftmost_binary_search([5], 3) == -1, "Single element less"
    
    # Test case 10: Single element - not found (greater)
    assert leftmost_binary_search([1], 3) == -1, "Single element greater"
    
    print("All tests passed! ✓")
 
 
if __name__ == "__main__":
    test_leftmost_binary_search()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

import bisect
 
def find_first_occurrence_bisect(arr: list, target: int) -> int:
    """
    Find first occurrence using Python's bisect_left.
    
    bisect_left returns the leftmost position where target 
    could be inserted while maintaining sorted order.
    This is EXACTLY our boundary position!
    """
    pos = bisect.bisect_left(arr, target)
    
    # bisect_left returns a position, not -1 for "not found"
    # We need to verify that the target actually exists at this position
    if pos < len(arr) and arr[pos] == target:
        return pos
    return -1
 
 
# Key insight: bisect_left always returns a valid insertion point
arr = [1, 2, 3, 3, 3, 3, 4, 5]
 
# For existing element: returns index of first occurrence
print(bisect.bisect_left(arr, 3))  # 2 (first 3)
 
# For non-existing element: returns where it WOULD go
print(bisect.bisect_left(arr, 3.5))  # 6 (between 3s and 4)
 
# For element less than all: returns 0
print(bisect.bisect_left(arr, 0))  # 0
 
# For element greater than all: returns len(arr)
print(bisect.bisect_left(arr, 100))  # 8
 
 
# IMPORTANT: bisect_left vs our function
# - bisect_left ALWAYS returns a valid index (0 to len(arr))
# - Our function returns -1 when target doesn't exist
# - Choose based on what your problem needs!
 
 
# Counting elements less than target
def count_less_than(arr: list, target: int) -> int:
    """
    Count how many elements are strictly less than target.
    This is just bisect_left(arr, target)!
    """
    return bisect.bisect_left(arr, target)
 
 
print(f"Elements less than 3: {count_less_than(arr, 3)}")  # 2
print(f"Elements less than 4: {count_less_than(arr, 4)}")  # 6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

import bisect
 
def leftmost_binary_search(arr: list, target: int) -> int:
    """Leftmost binary search with comprehensive edge case handling."""
    if not arr:
        return -1
    
    left, right = 0, len(arr)
    
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    
    if left < len(arr) and arr[left] == target:
        return left
    return -1
 
 
def verify_edge_cases():
    """
    Exhaustive edge case verification with explanations.
    Each case tests a specific boundary condition.
    """
    test_cases = [
        # (array, target, expected, description)
        ([], 3, -1, "Empty array"),
        ([3], 3, 0, "Single element - exact match"),
        ([5], 3, -1, "Single element - target smaller"),
        ([1], 3, -1, "Single element - target larger"),
        ([3, 4, 5], 3, 0, "Target is first element"),
        ([1, 2, 3], 3, 2, "Target is last element"),
        ([3, 3, 3, 3], 3, 0, "All elements match - return first"),
        ([5, 5, 5, 5], 3, -1, "All elements greater"),
        ([1, 1, 1, 1], 3, -1, "All elements smaller"),
        ([5, 6, 7, 8], 3, -1, "Target smaller than all elements"),
        ([1, 2, 3, 4], 10, -1, "Target larger than all elements"),
        ([1, 100], 50, -1, "Target falls in large gap"),
        ([3, 3, 5, 5], 3, 0, "Duplicates at start"),
        ([3, 3, 5, 5], 5, 2, "Duplicates at end"),
        ([1, 2, 3, 3, 3, 3, 4, 5], 3, 2, "Multiple occurrences in middle"),
        ([1, 1, 1, 1, 1, 1, 1, 2], 2, 7, "Single occurrence at very end"),
        ([1] * 1000 + [2], 2, 1000, "Large array with single match at end"),
        ([2] + [3] * 1000, 2, 0, "Large array with single match at start"),
        (list(range(1000)), 500, 500, "Sequential array"),
        (list(range(0, 1000, 2)), 500, 250, "Even numbers only - exact match"),
        (list(range(0, 1000, 2)), 501, -1, "Even numbers only - no match"),
    ]
    
    passed = 0
    failed = 0
    
    for arr, target, expected, description in test_cases:
        result = leftmost_binary_search(arr, target)
        if result == expected:
            passed += 1
            print(f"✓ {description}")
        else:
            failed += 1
            print(f"✗ {description}")
            print(f"  Array: {arr[:10]}{'...' if len(arr) > 10 else ''}")
            print(f"  Target: {target}, Expected: {expected}, Got: {result}")
    
    print(f"
{passed}/{passed + failed} tests passed")
    
    # Also verify against bisect.bisect_left for consistency
    print("
Verifying against bisect.bisect_left...")
    for arr, target, expected, description in test_cases:
        boundary = bisect.bisect_left(arr, target)
        our_result = leftmost_binary_search(arr, target)
        
        # Compare: bisect gives boundary, we give index or -1
        bisect_based = boundary if (boundary < len(arr) and arr[boundary] == target) else -1
        
        if our_result != bisect_based:
            print(f"  Mismatch! {description}")
            print(f"    Our result: {our_result}, bisect-based: {bisect_based}")
 
 
if __name__ == "__main__":
    verify_edge_cases()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

import bisect
from typing import List, Tuple, Optional
 
# Application 1: Count elements in a range
def count_in_range(arr: List[int], low: int, high: int) -> int:
    """
    Count elements where low <= element <= high.
    Uses leftmost search for lower bound and rightmost for upper bound.
    Time: O(log n)
    """
    left_boundary = bisect.bisect_left(arr, low)
    right_boundary = bisect.bisect_right(arr, high)
    return right_boundary - left_boundary
 
 
# Example: Count scores between 70 and 90
scores = [55, 60, 70, 72, 78, 85, 90, 92, 95, 100]
print(f"Scores in [70, 90]: {count_in_range(scores, 70, 90)}")  # 5
 
 
# Application 2: First event after timestamp
def first_event_after(events: List[Tuple[int, str]], timestamp: int) -> Optional[Tuple[int, str]]:
    """
    Find the first event that occurred at or after the given timestamp.
    Events are sorted by timestamp (first element of tuple).
    """
    if not events:
        return None
    
    # Extract timestamps for binary search
    timestamps = [e[0] for e in events]
    pos = bisect.bisect_left(timestamps, timestamp)
    
    if pos < len(events):
        return events[pos]
    return None
 
 
events = [
    (100, "start"),
    (150, "process"),
    (200, "validate"),
    (250, "complete"),
]
print(f"First event after 175: {first_event_after(events, 175)}")  # (200, 'validate')
 
 
# Application 3: IP Address Range Lookup
def find_network(ip_ranges: List[Tuple[int, int, str]], ip: int) -> Optional[str]:
    """
    Given sorted IP ranges (start, end, network_name), find which network an IP belongs to.
    IP ranges are sorted by start address.
    """
    if not ip_ranges:
        return None
    
    # Find the last range whose start <= ip
    starts = [r[0] for r in ip_ranges]
    pos = bisect.bisect_right(starts, ip) - 1
    
    if pos >= 0:
        start, end, name = ip_ranges[pos]
        if start <= ip <= end:
            return name
    return None
 
 
# Example IP ranges (using simple integers for clarity)
networks = [
    (0, 99, "Network A"),
    (100, 199, "Network B"),
    (200, 299, "Network C"),
]
print(f"IP 150 is in: {find_network(networks, 150)}")  # Network B
 
 
# Application 4: Grade assignment
def assign_grade(score: int) -> str:
    """
    Assign letter grade based on score.
    Uses binary search on thresholds.
    """
    thresholds = [60, 70, 80, 90]  # F, D, C, B, A
    grades = ['F', 'D', 'C', 'B', 'A']
    
    # Find first threshold >= score... wait, we want first threshold > score
    # Actually: find how many thresholds the score has exceeded
    pos = bisect.bisect_right(thresholds, score - 1)  # -1 because >= threshold gets that grade
    # Simpler: bisect_right tells us how many thresholds are <= score
    pos = bisect.bisect_right(thresholds, score)
    return grades[pos] if pos < len(grades) else grades[-1]
 
# Actually, cleaner version:
def assign_grade_v2(score: int) -> str:
    """Assign letter grade - cleaner implementation."""
    thresholds = [0, 60, 70, 80, 90]  # Minimum score for F, D, C, B, A
    grades = ['F', 'D', 'C', 'B', 'A']
    
    pos = bisect.bisect_right(thresholds, score) - 1
    return grades[pos]
 
 
for score in [55, 65, 75, 85, 95]:
    print(f"Score {score} => {assign_grade_v2(score)}")