6a:T405,function standardBinarySearch(arr: number[], target: number): number { /** * Standard binary search - returns ANY index containing target. * Returns -1 if target is not found. * * PROBLEM: No guarantee about WHICH occurrence is returned! */ let left = 0; let right = arr.length - 1; while (left <= right) { const mid = left + Math.floor((right - left) / 2); if (arr[mid] === target) { return mid; // Returns immediately upon finding ANY match } else if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1; } // Demonstration of the problem const arr = [1, 2, 3, 3, 3, 3, 4, 5]; const target = 3; const result = standardBinarySearch(arr, target); console.log(`Array: [${arr.join(', ')}]`); console.log(`Target: ${target}`); console.log(`Found at index: ${result}`); // Could be 2, 3, 4, or 5! console.log(`First occurrence is at: 2`); // But we need THIS6b:T437,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!6c:T42a,**Why the Invariant Guarantees Correctness:** 1. **Initialization**: When `left = 0` and `right = len(arr)`, the unexplored region is `[0, len(arr))` which is the entire array. The invariant is trivially satisfied—there are no elements to the left of `left` and no elements at or after `right`. 2. **Maintenance**: Each iteration shrinks the unexplored region while preserving the invariant: - If `arr[mid] < target`: We've proven that `mid` belongs to the left region. Setting `left = mid + 1` excludes it from unexplored while maintaining that all indices `< left` are `< target`. - If `arr[mid] >= target`: We've proven that `mid` belongs to the right region. Setting `right = mid` marks it as explored while maintaining that all indices `>= right` are `>= target`. 3. **Termination**: When `left == right`, the unexplored region `[left, right)` is empty. By the invariant: - All indices `< left` are `< target` - All indices `≥ left` are `>= target` - Therefore, `left` is exactly the boundary—the first index where `arr[left] >= target`.6d:Tbc4,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()6e:T85f,function leftmostBinarySearch(arr: number[], target: number): number { /** * 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) */ if (arr.length === 0) { return -1; // Handle empty array edge case } let left = 0; let right = arr.length; // Note: right is exclusive // Loop until unexplored region is empty while (left < right) { // Compute midpoint (avoiding integer overflow in other languages) const mid = left + Math.floor((right - left) / 2); if (arr[mid] < target) { // arr[mid] is in the left region (< target) left = mid + 1; } else { // arr[mid] >= target, might be first occurrence right = mid; } } // Check if we found the target if (left < arr.length && arr[left] === target) { return left; } return -1; } // Comprehensive test cases function testLeftmostBinarySearch(): void { const tests: [number[], number, number, string][] = [ [[1, 2, 3, 3, 3, 3, 4, 5], 3, 2, "Multiple occurrences"], [[1, 2, 3, 4, 5], 3, 2, "Single occurrence"], [[1, 2, 4, 5], 3, -1, "Target not present"], [[3, 3, 3, 3, 3], 3, 0, "All same elements"], [[1, 1, 1, 2, 3], 1, 0, "Target at beginning"], [[1, 2, 3, 5, 5, 5], 5, 3, "Target at end"], [[], 3, -1, "Empty array"], [[3], 3, 0, "Single element found"], [[5], 3, -1, "Single element less"], [[1], 3, -1, "Single element greater"], ]; for (const [arr, target, expected, description] of tests) { const result = leftmostBinarySearch(arr, target); console.assert( result === expected, `Failed: ${description}. Expected ${expected}, got ${result}` ); } console.log("All tests passed! ✓"); } testLeftmostBinarySearch();6f:T615,public class LeftmostBinarySearch { /** * Find the leftmost (first) occurrence of target in a sorted array. * * @param arr Sorted array of integers * @param target Value to search for * @return Index of first occurrence, or -1 if not found * * Time Complexity: O(log n) * Space Complexity: O(1) */ public static int leftmostBinarySearch(int[] arr, int target) { if (arr == null || arr.length == 0) { return -1; } int left = 0; int right = arr.length; // Exclusive right boundary while (left < right) { // Avoid integer overflow: use left + (right - left) / 2 int mid = left + (right - left) / 2; if (arr[mid] < target) { left = mid + 1; } else { right = mid; } } // Verify target exists if (left < arr.length && arr[left] == target) { return left; } return -1; } public static void main(String[] args) { // Test cases int[] arr = {1, 2, 3, 3, 3, 3, 4, 5}; System.out.println("First 3 at index: " + leftmostBinarySearch(arr, 3)); // 2 int[] allSame = {3, 3, 3, 3, 3}; System.out.println("First 3 in all-3s: " + leftmostBinarySearch(allSame, 3)); // 0 int[] notFound = {1, 2, 4, 5}; System.out.println("3 not found: " + leftmostBinarySearch(notFound, 3)); // -1 } }70:T66e,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)}") # 671:Tc87,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()72:Tcbf,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)}")62:{"json":{"id":"seed_f282e6b5e22b150f666ca36b51f89a63","slug":"binary-search-variations","category":"Data Structures & Algorithms","topic":"Binary Search Variations & Edge Cases","title":"Binary Search Variations & Edge Cases","description":"Master the critical variations of binary search that appear in real-world problems and interviews. Learn to find first occurrences, last occurrences, insertion positions, handle duplicates correctly, and avoid the notorious off-by-one errors that plague even experienced developers.","difficulty":"INTERMEDIATE","estimatedMinutes":90,"pages":[{"id":"seed_dbe0e6719e15bda98aa1b096249f6a8b","title":"Finding First Occurrence","order":0,"content":[{"id":"opening-hook","title":"Beyond Simple Lookup","content":[{"data":{"content":"Standard binary search answers a simple question: **\"Is this element present in the sorted array?\"** But real-world problems rarely ask such simple questions. Consider these variations:\n\n- \"What is the **first** day our revenue exceeded $1M?\"\n- \"Find the **leftmost** position where a target value appears.\"\n- \"How many elements are **strictly less than** a given threshold?\"\n- \"At what index should we insert a value to **maintain sorted order**?\"\n\nThese questions all share a common structure: they require finding a **boundary** in a sorted sequence. Standard binary search falls short because it arbitrarily returns *any* matching position—but we need the *specific* position that marks the boundary.\n\nThis page introduces **leftmost binary search** (also called **lower bound search**), the foundational technique for finding the first occurrence of a target value. Mastering this pattern unlocks a family of powerful variations that form the backbone of advanced binary search applications."},"type":"text"},{"data":{"icon":"Target","title":"What You Will Learn","content":"By the end of this page, you will understand: (1) Why standard binary search fails for boundary-finding problems, (2) The loop invariant technique for designing correct binary search variants, (3) The leftmost binary search algorithm with rigorous proof of correctness, (4) How to handle all edge cases including empty arrays, missing targets, and all-matching arrays.","variant":"info"},"type":"callout"}]},{"id":"problem-with-standard","title":"The Problem with Standard Binary Search","content":[{"data":{"content":"Let's begin by understanding precisely why standard binary search is insufficient for finding the first occurrence of a target. This understanding will motivate our solution.\n\n**Standard Binary Search Behavior:**\n\nConsider the sorted array `[1, 2, 3, 3, 3, 3, 4, 5]` and target `3`. Standard binary search might return:\n- Index 2 (the first 3)\n- Index 3 (the second 3)\n- Index 4 (the third 3)\n- Index 5 (the fourth 3)\n\nWhich index gets returned depends entirely on how the array happens to partition during the search. Standard binary search makes no guarantee about *which* matching element it finds—it only guarantees finding *some* matching element in O(log n) time."},"type":"text"},{"data":{"fileName":"standard_binary_search.py","languages":[{"code":"def standard_binary_search(arr, target):\n \"\"\"\n Standard binary search - returns ANY index containing target.\n Returns -1 if target is not found.\n \n PROBLEM: No guarantee about WHICH occurrence is returned!\n \"\"\"\n left, right = 0, len(arr) - 1\n \n while left <= right:\n mid = left + (right - left) // 2\n \n if arr[mid] == target:\n return mid # Returns immediately upon finding ANY match\n elif arr[mid] < target:\n left = mid + 1\n else:\n right = mid - 1\n \n return -1\n\n# Demonstration of the problem\narr = [1, 2, 3, 3, 3, 3, 4, 5]\ntarget = 3\n\nresult = standard_binary_search(arr, target)\nprint(f\"Array: {arr}\")\nprint(f\"Target: {target}\")\nprint(f\"Found at index: {result}\") # Could be 2, 3, 4, or 5!\nprint(f\"First occurrence is at: 2\") # But we need THIS","label":"Python","value":"python"},{"code":"$6a","label":"TypeScript","value":"typescript"}]},"type":"code"},{"data":{"content":"**The Core Issue:**\n\nThe problem lies in the **early termination** on line where we `return mid` immediately when `arr[mid] == target`. The algorithm doesn't know whether there are more matching elements to the *left* of this position. Perhaps there are, perhaps there aren't—but the algorithm never checks.\n\n**Naive Fix Attempt:**\n\nA tempting but flawed approach is to find any match and then scan leftward:"},"type":"text"},{"data":{"fileName":"naive_first_occurrence.py","languages":[{"code":"$6b","label":"Python","value":"python"}]},"type":"code"},{"data":{"icon":"AlertCircle","title":"The Naive Approach Destroys Our Complexity Guarantee","content":"When all elements in the array equal the target, the naive approach degrades to O(n) linear time. This is unacceptable—we need an algorithm that maintains O(log n) time complexity regardless of how many duplicates exist. The solution requires fundamentally rethinking how binary search should behave when it finds a match.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":1},{"id":"boundary-finding-perspective","title":"The Boundary-Finding Perspective","content":[{"data":{"content":"To design a correct leftmost binary search, we need to shift our mental model from **element finding** to **boundary finding**. This conceptual shift is crucial for understanding all binary search variants.\n\n**The Key Insight:**\n\nInstead of asking \"Where is the target?\", we ask:\n\n> **\"Where is the boundary between elements less than the target and elements greater than or equal to the target?\"**\n\nThis boundary is precisely where the first occurrence of the target would be (if it exists). Let's visualize this:"},"type":"text"},{"data":{"height":"280px","mermaidSyntax":"graph LR\n subgraph Array[\"Sorted Array: [1, 2, 3, 3, 3, 3, 4, 5]\"]\n A[\"1\"] --> B[\"2\"] --> C[\"3\"] --> D[\"3\"] --> E[\"3\"] --> F[\"3\"] --> G[\"4\"] --> H[\"5\"]\n end\n \n subgraph Partition[\"Binary Partition View\"]\n L[\"< target (3)\"] --> |\"boundary\"| R[\">= target (3)\"]\n end\n \n subgraph Indices\n I0[\"idx 0: 1\"] --> I1[\"idx 1: 2\"] --> I2[\"idx 2: 3\"] --> I3[\"idx 3: 3\"]\n end"},"type":"mermaid-excalidraw"},{"data":{"content":"**Partitioning the Array:**\n\nFor any sorted array and target value, we can conceptually partition the array into two regions:"},"type":"text"},{"data":{"rows":[["**Left Region**","All elements `< target`","Indices 0, 1 (values 1, 2)"],["**Right Region**","All elements `≥ target`","Indices 2, 3, 4, 5, 6, 7 (values 3, 3, 3, 3, 4, 5)"]],"headers":["Region","Elements","Indices (for target=3)"]},"type":"table"},{"data":{"content":"The **boundary** is the first index of the right region—which is exactly what we want!\n\n**Critical Observations:**\n\n1. If the target exists in the array, the boundary points to its **first occurrence**.\n2. If the target doesn't exist, the boundary points to where it **should be inserted** to maintain sorted order.\n3. The boundary is always well-defined, even for edge cases (it could be 0 or len(arr))."},"type":"text"},{"data":{"icon":"Lightbulb","title":"The Predicate Function","content":"Boundary-finding binary search works by evaluating a **predicate function** at each position. For leftmost search, the predicate is `arr[i] >= target`. The predicate is False for all elements in the left region and True for all elements in the right region. We're searching for the first True (the transition point from False to True).","variant":"tip"},"type":"callout"},{"data":{"rows":[["0","1","False","Left (< target)"],["1","2","False","Left (< target)"],["2","3","True","Right (≥ target) ← FIRST TRUE"],["3","3","True","Right (≥ target)"],["4","3","True","Right (≥ target)"],["5","3","True","Right (≥ target)"],["6","4","True","Right (≥ target)"],["7","5","True","Right (≥ target)"]],"caption":"Predicate Evaluation for target = 3","headers":["Index","Value","Predicate: value ≥ 3","Region"]},"type":"table"},{"data":{"content":"**Why This Model Works:**\n\nThe power of this model is that it transforms an ambiguous question (\"which matching element?\") into an unambiguous one (\"where is the boundary?\"). Every sorted array has exactly one boundary for any given target—including arrays with zero, one, or many occurrences of the target.\n\nThis model also reveals why binary search works on this problem: the predicate function is **monotonic** (once it becomes True, it stays True). Any monotonic predicate can be searched in O(log n) time using binary search."},"type":"text"}],"titleType":"number","titleNumber":2},{"id":"loop-invariant-approach","title":"The Loop Invariant Approach","content":[{"data":{"content":"Binary search variants are notoriously error-prone. Even experienced engineers struggle with off-by-one errors, infinite loops, and incorrect boundary handling. The key to writing correct binary search code is using **loop invariants**—precise mathematical statements that remain true throughout the algorithm's execution.\n\n**What is a Loop Invariant?**\n\nA loop invariant is a condition that:\n1. Is **true before** the loop begins (initialization)\n2. **Remains true** after each iteration (maintenance)\n3. When the loop terminates, **proves our goal** (termination)\n\nFor leftmost binary search, we'll use two pointers: `left` and `right`. The invariant precisely describes what these pointers represent throughout the algorithm."},"type":"text"},{"data":{"icon":"Info","title":"The Leftmost Binary Search Invariant","content":"**Invariant**: At all times during execution:\n• All elements at indices `< left` are definitely `< target` (the left region)\n• All elements at indices `≥ right` are definitely `≥ target` (the right region)\n• Elements in the range `[left, right)` are **unexplored**\n\nWhen the loop terminates (`left == right`), the unexplored region is empty, and `left` points to the boundary—the first position where `arr[i] ≥ target`.","variant":"note"},"type":"callout"},{"data":{"content":"**Visualizing the Invariant:**\n\nAt any point during execution, the array looks like this:\n\n```\n[ definitely < target ][ unexplored ][ definitely >= target ]\n | | |\n 0 left right len(arr)\n```\n\nLet's trace through an example to see how the invariant is maintained:"},"type":"text"},{"data":{"rows":[["Init","0","8","-","-","-","Setup","Trivially true: unexplored = [0,8)"],["1","0","8","4","3","3 >= 3","right = 4","Now [4,8) is >= target ✓"],["2","0","4","2","3","3 >= 3","right = 2","Now [2,8) is >= target ✓"],["3","0","2","1","2","2 < 3","left = 2","Now [0,2) is < target ✓"],["End","2","2","-","-","-","Exit loop","left == right == 2, boundary found!"]],"caption":"Invariant Trace: Finding first 3 in [1, 2, 3, 3, 3, 3, 4, 5]","headers":["Iteration","left","right","mid","arr[mid]","Comparison","Action","Invariant Status"]},"type":"table"},{"data":{"content":"$6c"},"type":"text"},{"data":{"icon":"Lightbulb","title":"Why right = mid (not mid - 1)?","content":"This is a crucial detail. When `arr[mid] >= target`, we know `mid` is in the right region, but `mid` might be the FIRST element of the right region—it could be our answer! We can't exclude it. Setting `right = mid` marks it as explored (the new right boundary) without losing it as a potential answer. Setting `right = mid - 1` would be incorrect and could skip the answer entirely.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":3},{"id":"the-algorithm","title":"The Leftmost Binary Search Algorithm","content":[{"data":{"content":"Now we can implement the algorithm with confidence, knowing exactly why each line is correct based on our loop invariant.\n\n**Algorithm Overview:**\n\n1. Initialize `left = 0`, `right = len(arr)` (note: right is exclusive)\n2. While `left < right` (unexplored region is non-empty):\n - Compute `mid = left + (right - left) // 2`\n - If `arr[mid] < target`: `left = mid + 1`\n - Else (if `arr[mid] >= target`): `right = mid`\n3. Return `left` (the boundary position)\n4. Check if `arr[left] == target` to confirm the target exists"},"type":"text"},{"data":{"fileName":"leftmost_binary_search.py","languages":[{"code":"$6d","label":"Python","value":"python"},{"code":"$6e","label":"TypeScript","value":"typescript"},{"code":"$6f","label":"Java","value":"java"}]},"type":"code"},{"data":{"icon":"AlertCircle","title":"Critical Implementation Details","content":"Three details often cause bugs:\n\n1. **right = len(arr)** (not len(arr) - 1) — The boundary could be at index len(arr) if all elements are less than target.\n\n2. **Loop condition: left < right** (not left <= right) — We stop when the unexplored region is empty.\n\n3. **right = mid** (not mid - 1) — When arr[mid] >= target, mid could be the answer; don't skip it!","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":4},{"id":"library-implementations","title":"Library Implementations: bisect_left","content":[{"data":{"content":"Most programming languages provide built-in functions for leftmost binary search. Understanding these library functions—and their subtle differences from our implementation—is essential for practical programming.\n\n**Python: bisect.bisect_left**\n\nPython's `bisect` module provides `bisect_left`, which finds the leftmost position where an element could be inserted to maintain sorted order. This is exactly our boundary-finding operation!"},"type":"text"},{"data":{"fileName":"using_bisect_left.py","languages":[{"code":"$70","label":"Python","value":"python"}]},"type":"code"},{"data":{"rows":[["Python","bisect.bisect_left(a, x)","Insertion point (index)","Always returns valid index 0 to len(a)"],["C++","std::lower_bound(begin, end, x)","Iterator to first >= x","Returns end iterator if all elements < x"],["Java","Arrays.binarySearch(a, x)","Index or -(insertion point + 1)","Negative means not found; decode with -(result + 1)"],["C#","Array.BinarySearch(a, x)","Index or ~(insertion point)","Use bitwise NOT to get insertion point if negative"],["Go","sort.SearchInts(a, x)","Insertion point (index)","Returns len(a) if all elements < x"]],"caption":"Library Functions for Leftmost Binary Search","headers":["Language","Function","Returns","Notes"]},"type":"table"},{"data":{"icon":"Lightbulb","title":"Java's Encoding Scheme","content":"Java's `Arrays.binarySearch` uses a clever encoding: if the element is found, it returns the index; if not found, it returns `-(insertionPoint + 1)`. To extract the insertion point for a 'not found' result: `insertionPoint = -(result + 1)` or equivalently `insertionPoint = ~result` (bitwise NOT). However, note that Java's binarySearch doesn't guarantee finding the FIRST occurrence—you may need to implement leftmost search yourself.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":5},{"id":"edge-cases-validation","title":"Comprehensive Edge Case Analysis","content":[{"data":{"content":"A robust implementation must handle all edge cases correctly. Let's analyze each case systematically, verifying our algorithm's behavior at the extremes."},"type":"text"},{"data":{"rows":[["Empty array","[]","3","-1","0","No elements to search"],["Single element - found","[3]","3","0","0","Only element matches"],["Single element - too small","[5]","3","-1","0","Target would go before"],["Single element - too large","[1]","3","-1","1","Target would go after"],["Target at start","[3, 4, 5]","3","0","0","First element matches"],["Target at end","[1, 2, 3]","3","2","2","Last element matches"],["All same (matches)","[3, 3, 3, 3]","3","0","0","First of many matches"],["All same (no match)","[5, 5, 5, 5]","3","-1","0","None match, all greater"],["Target smaller than all","[5, 6, 7, 8]","3","-1","0","Would insert at start"],["Target larger than all","[1, 2, 3, 4]","10","-1","4","Would insert at end"],["Large gap","[1, 100]","50","-1","1","Target falls in gap"],["Duplicates at boundaries","[3, 3, 5, 5]","5","2","2","First of last group"]],"caption":"Edge Cases for Leftmost Binary Search","headers":["Edge Case","Array","Target","Expected Result","Boundary Position","Notes"]},"type":"table"},{"data":{"fileName":"edge_case_testing.py","languages":[{"code":"$71","label":"Python","value":"python"}]},"type":"code"},{"data":{"icon":"AlertCircle","title":"The Subtle Array-of-One-Element Case","content":"A single-element array is surprisingly tricky to reason about. With `arr = [5]` and `target = 3`, our algorithm sets `left=0, right=1`. First iteration: `mid=0`, `arr[0]=5 >= 3`, so `right=0`. Now `left == right == 0`. Check: `arr[0]=5 != 3`, so return -1. Correct! The algorithm works because the invariant holds even for the smallest non-empty arrays.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":6},{"id":"applications","title":"Real-World Applications","content":[{"data":{"content":"Leftmost binary search is a fundamental building block for many practical problems. Here are several important applications:"},"type":"text"},{"data":{"items":["**Counting Elements Less Than Target** — The boundary position is exactly the count of elements strictly less than target. For `[1,2,3,3,3,4,5]` with target 3, boundary = 2 = count of elements < 3.","**Finding Range of Duplicates** — Combined with rightmost search (next page), you can find the full range [first, last] of a value in O(log n).","**Time-Series Queries** — \"What was the first reading above threshold X?\" is a leftmost search on timestamp-sorted data.","**Database Indexing** — B-tree indexes use lower-bound searches for range queries like `WHERE date >= '2024-01-01'`.","**Version Bisection** — Finding the first commit that introduced a bug is leftmost search on git history.","**Scheduling Problems** — Finding the first available time slot that can accommodate a meeting duration."],"title":{"icon":"Target","text":"Key Applications of Leftmost Binary Search","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"fileName":"practical_applications.py","languages":[{"code":"$72","label":"Python","value":"python"}]},"type":"code"}],"titleType":"number","titleNumber":7},{"id":"summary-key-takeaways","title":"Summary: Mastering Leftmost Binary Search","content":[{"data":{"content":"Finding the first occurrence of a target in a sorted array is a fundamental skill that extends far beyond simple element lookup. Let's consolidate what we've learned:"},"type":"text"},{"data":{"type":"ordered","items":["**Standard binary search is insufficient** — It finds *any* match, not necessarily the first. Naive post-search scanning destroys O(log n) complexity.","**Think in terms of boundaries** — Leftmost search finds the transition point from elements < target to elements >= target. This boundary is always well-defined.","**Use loop invariants** — Maintain that everything left of `left` is < target, and everything >= `right` is >= target. This guarantees correctness.","**Critical details matter** — Use `right = len(arr)` (exclusive), `left < right` for loop condition, and `right = mid` (not `mid - 1`) when `arr[mid] >= target`.","**Library functions vary** — Python's `bisect_left`, C++'s `lower_bound`, and Java's `binarySearch` behave differently. Know your language's semantics.","**Always test edge cases** — Empty arrays, single elements, all-same arrays, targets at boundaries, and targets not present are critical to verify."],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"rows":[["Time Complexity","O(log n)"],["Space Complexity","O(1)"],["Loop Condition","left < right"],["Initial left","0"],["Initial right","len(arr) (exclusive)"],["When arr[mid] < target","left = mid + 1"],["When arr[mid] >= target","right = mid"],["Result","left = boundary position"],["Final Check","arr[left] == target?"]],"caption":"Quick Reference: Leftmost Binary Search","headers":["Property","Value"]},"type":"table"},{"data":{"content":"**What's Next:**\n\nIn the next page, we'll explore **Finding Last Occurrence** (rightmost binary search). You'll see how a simple modification to our predicate and update rules gives us the symmetric operation—finding the rightmost position of a target. Together, leftmost and rightmost search form a powerful toolkit for range queries and duplicate handling."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"You've mastered the foundational technique of leftmost binary search. You understand why standard binary search fails, how to reason with loop invariants, and how to handle all edge cases. This pattern—finding a boundary in a sorted sequence—will appear repeatedly as we explore more binary search variations.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":8}],"isLocked":false},{"id":"seed_2fb7406306e4cf4d332a6150814aef22","title":"Finding Last Occurrence","order":1,"content":null,"isLocked":true},{"id":"seed_7ca71fbe222cafdc8cb8bde13dce21ce","title":"Finding Insertion Position","order":2,"content":null,"isLocked":true},{"id":"seed_32ae5ae4520533e7c823111e8537e09c","title":"Handling Duplicates Correctly","order":3,"content":null,"isLocked":true},{"id":"seed_fab6cff794f2f6174e413070ed8e88df","title":"Off-by-One Errors and How to Avoid Them","order":4,"content":null,"isLocked":true}]}}