Back
+30 XP
Concept

Binary Search with Left/Right Boundary Duplicates

Standard binary search stops at an arbitrary matching element. In sorted index arrays containing duplicate timestamps or keys, database range scans require pinpointing the exact first and last occurrences of a target in strictly $O(\log N)$ logarithmic time 🎯📐⚡.

python
def find_leftmost(arr, target):
    l, r, ans = 0, len(arr) - 1, -1
    while l <= r:
        m = (l + r) // 2
        if arr[m] == target: ans = m; r = m - 1
        elif arr[m] < target: l = m + 1
        else: r = m - 1
    return ans

print("First occurrence of 8:", find_leftmost([5, 7, 8, 8, 8, 10], 8))

# 26. Binary Search with Left/Right Boundary Duplicates In time-series databases and LSM-Tree storage segments, identical keys (like events occurring at timestamp `1700000000`) cluster together in sorted order. If you need to scan all entries for that timestamp, finding an arbitrary match is insufficient 🛑. ```python # The Duplicates Dilemma: # Array: [5, 7, 7, 8, 8, 8, 8, 10] # Indices:0 1 2 3 4 5 6 7 # # Standard Binary Search on 8 might land on index 4 or 5 and stop. # Left Boundary: Index 3 (First 8) # Right Boundary: Index 6 (Last 8) # Total Occurrences = (6 - 3) + 1 = 4 items ``` ### The Boundary Pointer Maneuver - **Finding Leftmost**: When `nums[mid] == target`, don't return! Record `ans = mid` and force `right = mid - 1`. The loop continues bisecting the left subarray until exhausted. - **Finding Rightmost**: When `nums[mid] == target`, record `ans = mid` and force `left = mid + 1`. The loop continues bisecting the right subarray. - Two logarithmic passes: **Strict $O(\log N)$ time, $O(1)$ space** 🎯📐⚡! --- ### Interactive Pop-Quiz 🧠 #### When nums[mid] == target, how does the leftmost boundary search differ from standard binary search? - [ ] It records mid as a candidate and shrinks the right pointer `right = mid - 1` to keep searching leftward for earlier occurrences 🎯 - [ ] It returns mid immediately - [ ] It switches execution to a linear O(N) scan - [ ] It sorts the array in descending order --- ### Practical Challenge 🎯 Implement `find_boundaries(nums: list[int], target: int) -> tuple[int, int]` returning the 0-indexed `(first_idx, last_idx)` of `target` in a sorted array (or `(-1, -1)` if absent). Perform both searches in $O(\log N)$ time. Test with `nums = [5, 7, 7, 8, 8, 8, 8, 10]`, verifying target 8 yields `(3, 6)`, target 7 yields `(1, 2)`, and target 6 yields `(-1, -1)`. Print results. <details> <summary>Solution</summary> ```python def find_first(nums: list[int], target: int) -> int: left, right = 0, len(nums) - 1 first_idx = -1 while left <= right: mid = (left + right) // 2 if nums[mid] == target: first_idx = mid right = mid - 1 elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return first_idx def find_last(nums: list[int], target: int) -> int: left, right = 0, len(nums) - 1 last_idx = -1 while left <= right: mid = (left + right) // 2 if nums[mid] == target: last_idx = mid left = mid + 1 elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return last_idx def find_boundaries(nums: list[int], target: int) -> tuple[int, int]: return (find_first(nums, target), find_last(nums, target)) data = [5, 7, 7, 8, 8, 8, 8, 10] b8 = find_boundaries(data, 8) b7 = find_boundaries(data, 7) b6 = find_boundaries(data, 6) assert b8 == (3, 6) assert b7 == (1, 2) assert b6 == (-1, -1) print(f"Boundaries verified: target 8 -> {b8}, target 7 -> {b7}, target 6 -> {b6}") ``` </details>

Checkpoint

When `nums[mid] == target`, how does the leftmost boundary search differ from standard binary search? 🧠

Practice

Implement `find_boundaries(nums: list[int], target: int) -> tuple[int, int]` returning the 0-indexed `(first_idx, last_idx)` of `target` in a sorted array (or `(-1, -1)` if absent). Perform both searches in $O(\log N)$ time. Test with `nums = [5, 7, 7, 8, 8, 8, 8, 10]`, verifying target 8 yields `(3, 6)`, target 7 yields `(1, 2)`, and target 6 yields `(-1, -1)`. Print results. 🎯

Terminal
01
Tap code blocks below to assemble
Available Blocks