7a:T44c,def binary_search(arr: list[int], target: int) -> int: """ Standard binary search implementation. Returns index of target if found, -1 otherwise. Precondition: arr is sorted in ascending order Time Complexity: O(log n) Space Complexity: O(1) """ left, right = 0, len(arr) - 1 while left <= right: # Calculate mid, avoiding integer overflow mid = left + (right - left) // 2 if arr[mid] == target: return mid # Found it! elif arr[mid] < target: left = mid + 1 # Target is in right half else: right = mid - 1 # Target is in left half return -1 # Not found # Example usage and trace arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] target = 23 # Trace: # Iteration 1: left=0, right=9, mid=4, arr[4]=16 < 23 → left=5 # Iteration 2: left=5, right=9, mid=7, arr[7]=56 > 23 → right=6 # Iteration 3: left=5, right=6, mid=5, arr[5]=23 == 23 → return 5 result = binary_search(arr, target) print(f"Found {target} at index {result}") # Output: Found 23 at index 57b:T4d7,function binarySearch(arr: number[], target: number): number { /** * Standard binary search implementation. * Returns index of target if found, -1 otherwise. * * Precondition: arr is sorted in ascending order * Time Complexity: O(log n) * Space Complexity: O(1) */ let left = 0; let right = arr.length - 1; while (left <= right) { // Calculate mid, avoiding integer overflow const mid = left + Math.floor((right - left) / 2); if (arr[mid] === target) { return mid; // Found it! } else if (arr[mid] < target) { left = mid + 1; // Target is in right half } else { right = mid - 1; // Target is in left half } } return -1; // Not found } // Example usage and trace const arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]; const target = 23; // Trace: // Iteration 1: left=0, right=9, mid=4, arr[4]=16 < 23 → left=5 // Iteration 2: left=5, right=9, mid=7, arr[7]=56 > 23 → right=6 // Iteration 3: left=5, right=6, mid=5, arr[5]=23 == 23 → return 5 const result = binarySearch(arr, target); console.log(`Found ${target} at index ${result}`); // Output: Found 23 at index 57c:T64f,def binary_search_recursive(arr: list[int], target: int, left: int, right: int) -> int: """ Recursive binary search explicitly showing D&C structure. DIVIDE: Calculate midpoint to split the search space CONQUER: Recursively search the appropriate half COMBINE: Return the result (trivial in this case) """ # BASE CASE: Search space is empty if left > right: return -1 # Target not found # DIVIDE: Split the search space mid = left + (right - left) // 2 # BASE CASE: Found the target if arr[mid] == target: return mid # CONQUER: Search exactly ONE subproblem if arr[mid] < target: # Target must be in right half return binary_search_recursive(arr, target, mid + 1, right) else: # Target must be in left half return binary_search_recursive(arr, target, left, mid - 1) # COMBINE: Implicit — we simply return the recursive result def binary_search(arr: list[int], target: int) -> int: """Wrapper for the recursive implementation.""" return binary_search_recursive(arr, target, 0, len(arr) - 1) # Trace the D&C structure: arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] target = 23 # Call: binary_search_recursive(arr, 23, 0, 9) # DIVIDE: mid = 4, arr[4] = 16 < 23 # CONQUER: binary_search_recursive(arr, 23, 5, 9) # DIVIDE: mid = 7, arr[7] = 56 > 23 # CONQUER: binary_search_recursive(arr, 23, 5, 6) # DIVIDE: mid = 5, arr[5] = 23 == 23 # BASE CASE: return 5 # COMBINE: return 5 # COMBINE: return 5 # Result: 57d:T626,def find_first_occurrence(arr: list[int], target: int) -> int: """ Find the FIRST occurrence of target in a sorted array. Demonstrates how modifying the D&C pattern yields variants. Key insight: When we find target, we don't stop immediately. Instead, we continue searching LEFT to find earlier occurrences. """ left, right = 0, len(arr) - 1 result = -1 while left <= right: mid = left + (right - left) // 2 if arr[mid] == target: result = mid # Record this occurrence right = mid - 1 # But keep searching left! elif arr[mid] < target: left = mid + 1 else: right = mid - 1 return result def find_last_occurrence(arr: list[int], target: int) -> int: """ Find the LAST occurrence of target in a sorted array. Mirror of find_first_occurrence. """ left, right = 0, len(arr) - 1 result = -1 while left <= right: mid = left + (right - left) // 2 if arr[mid] == target: result = mid # Record this occurrence left = mid + 1 # But keep searching right! elif arr[mid] < target: left = mid + 1 else: right = mid - 1 return result # Example arr = [2, 4, 4, 4, 4, 6, 8] print(f"First occurrence of 4: {find_first_occurrence(arr, 4)}") # 1 print(f"Last occurrence of 4: {find_last_occurrence(arr, 4)}") # 4 print(f"Count of 4s: {find_last_occurrence(arr, 4) - find_first_occurrence(arr, 4) + 1}") # 472:{"json":{"id":"seed_33d342895a5fbd345411052e7d384795","slug":"binary-search-as-dc","category":"Data Structures & Algorithms","topic":"Binary Search as D&C","title":"Binary Search as Divide and Conquer","description":"Reframe binary search as a divide-and-conquer algorithm. Understand how the classic search algorithm embodies the D&C paradigm through intelligent space division, strategic elimination, and result synthesis.","difficulty":"INTERMEDIATE","estimatedMinutes":50,"pages":[{"id":"seed_1f6cc6af552fa7140209311df76ea143","title":"Binary Search Through the D&C Lens","order":0,"content":[{"id":"opening-hook","title":"Seeing Familiar Algorithms in a New Light","content":[{"data":{"content":"You've almost certainly encountered binary search before—perhaps as one of the first 'clever' algorithms you learned. It's elegant, fast, and practically ubiquitous. But have you ever stopped to consider *why* binary search works so well? What underlying principle makes it so efficient?\n\nThe answer lies in recognizing binary search as a **divide-and-conquer algorithm**. While this might seem obvious in retrospect, explicitly viewing binary search through the D&C lens reveals deep insights about algorithm design, helps you recognize similar patterns in other problems, and transforms binary search from a memorized trick into a principled approach."},"type":"text"},{"data":{"icon":"Target","title":"What You Will Learn","content":"By the end of this page, you will understand how binary search exemplifies the divide-and-conquer paradigm, how viewing it through this lens deepens your understanding of algorithmic efficiency, and how the D&C perspective opens doors to variants and generalizations you might otherwise miss.","variant":"info"},"type":"callout"}]},{"id":"revisiting-binary-search","title":"Revisiting Binary Search","content":[{"data":{"content":"Before we dissect binary search as a D&C algorithm, let's establish a solid foundation by revisiting the algorithm itself. Understanding the mechanics precisely is prerequisite to seeing the pattern.\n\n**The Problem:**\n\nGiven a **sorted array** of n elements and a **target value**, determine whether the target exists in the array, and if so, return its index.\n\n**The Naive Approach:**\n\nThe obvious solution is linear search: examine each element sequentially until you find the target or exhaust the array. This takes O(n) time. For an array of 1 million elements, you might need up to 1 million comparisons.\n\n**Binary Search's Insight:**\n\nBinary search exploits the **sorted property** of the data. By examining the middle element, you can immediately determine which half of the array might contain the target—and discard the other half entirely. This cuts the problem size in half with each step."},"type":"text"},{"data":{"fileName":"binary_search.py","languages":[{"code":"$7a","label":"Python","value":"python"},{"code":"$7b","label":"TypeScript","value":"typescript"}]},"type":"code"},{"data":{"content":"**Key Observations:**\n\n1. **Each iteration halves the search space** — If we start with n elements, after one comparison we have at most n/2, then n/4, then n/8, and so on.\n\n2. **The algorithm terminates quickly** — After log₂(n) iterations, the search space reduces to a single element (or zero elements if not found).\n\n3. **The sorted property is essential** — Without ordering, we cannot safely discard half the elements.\n\nThese observations hint at the divide-and-conquer nature of the algorithm. Let's make this connection explicit."},"type":"text"}],"titleType":"number","titleNumber":1},{"id":"dc-paradigm-recap","title":"The D&C Paradigm — A Quick Recap","content":[{"data":{"content":"Before mapping binary search onto the D&C framework, let's briefly recall what divide-and-conquer entails. The paradigm consists of three canonical phases:"},"type":"text"},{"data":{"items":["**DIVIDE** — Break the problem into one or more smaller subproblems of the same type. The key is that subproblems should be independent (solutions don't affect each other) and smaller (progress toward base case).","**CONQUER** — Solve each subproblem recursively. If the subproblem is small enough (base case), solve it directly without further division.","**COMBINE** — Merge the subproblem solutions to obtain the solution to the original problem. This might be trivial or might require significant work."],"title":{"icon":"Target","text":"The Three Phases of Divide and Conquer","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**Classic D&C Examples:**\n\n- **Merge Sort**: Divide array in half → Sort each half recursively → Merge sorted halves\n- **Quick Sort**: Partition around pivot → Sort partitions recursively → Concatenate (trivial)\n- **Strassen's Matrix Multiplication**: Divide matrices into quadrants → Multiply submatrices → Combine with additions\n\nNotice that classic D&C algorithms typically:\n1. Create **multiple** subproblems (usually 2)\n2. **Solve all** subproblems\n3. Perform **non-trivial combination**\n\nBinary search is fascinating because it deviates from this pattern in subtle but important ways. Let's see how."},"type":"text"},{"data":{"icon":"Info","title":"D&C Variations","content":"Not all divide-and-conquer algorithms look identical. Some divide into many parts (k-way merge), some solve only one subproblem (decrease-and-conquer), and some have trivial combination steps. Binary search represents a streamlined variant where division and selection happen simultaneously.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":2},{"id":"mapping-binary-search","title":"Mapping Binary Search to the D&C Framework","content":[{"data":{"content":"Now let's explicitly decompose binary search into the three phases of divide-and-conquer. This mapping reveals the algorithm's underlying structure:"},"type":"text"},{"data":{"rows":[["DIVIDE","Split the search space into two halves at the midpoint","The sorted property guarantees elements are partitioned by value"],["CONQUER","Search the appropriate half (left if target < mid, right if target > mid)","Only ONE subproblem needs solving—the other is eliminated"],["COMBINE","Return the result directly","Combination is trivial because we only solved one subproblem"]],"caption":"Binary Search as Divide-and-Conquer","headers":["D&C Phase","Binary Search Implementation","Key Insight"]},"type":"table"},{"data":{"content":"**The Key Distinction — Decrease-and-Conquer:**\n\nBinary search is sometimes classified as **decrease-and-conquer** rather than divide-and-conquer. The distinction:\n\n- **Divide-and-Conquer**: Divide into multiple parts, solve **all** subproblems, then combine\n- **Decrease-and-Conquer**: Divide into parts, but solve only **one** subproblem (others are eliminated)\n\nBinary search is a textbook decrease-and-conquer algorithm: we divide the array into two halves, but we only need to search **one** of them. The other half is eliminated entirely based on the comparison with the middle element.\n\nHowever, decrease-and-conquer is fundamentally a *specialization* of the D&C paradigm, not a departure from it. Viewing binary search as D&C remains valid and illuminating."},"type":"text"},{"data":{"fileName":"binary_search_recursive.py","languages":[{"code":"$7c","label":"Python","value":"python"}]},"type":"code"},{"data":{"icon":"Lightbulb","title":"The Recursive View Clarifies Structure","content":"While iterative binary search is typically preferred in practice (due to O(1) space), the recursive version makes the D&C structure explicit. Each recursive call represents the 'conquer' phase, the midpoint calculation is 'divide', and the return propagation is the (trivial) 'combine' phase.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":3},{"id":"why-perspective-matters","title":"Why This Perspective Matters","content":[{"data":{"content":"You might wonder: \"Binary search works the same regardless of how we categorize it. Why bother with the D&C framing?\"\n\nThis is a fair question, and the answer reveals something profound about algorithmic thinking. Viewing binary search as D&C provides several benefits:"},"type":"text"},{"data":{"items":["**Unified Understanding** — Instead of memorizing binary search as an isolated technique, you recognize it as an instance of a general principle. This reduces cognitive load and improves retention.","**Complexity Analysis** — The D&C perspective connects directly to the Master Theorem. Binary search has recurrence T(n) = T(n/2) + O(1), immediately yielding O(log n).","**Pattern Recognition** — Many problems that don't look like 'search' at first can be solved with binary search once you recognize the D&C structure (e.g., binary search on answer space).","**Generalization** — Understanding the D&C pattern helps you generalize: ternary search, k-way search, search in rotated arrays all follow similar patterns with variations.","**Problem Design** — When designing new algorithms, the D&C framework provides a template: identify how to divide, how to select subproblems, and how to combine."],"title":{"icon":"Sparkles","text":"Benefits of the D&C Perspective","type":"icon","color":"primary","variant":"outline-circle"},"variant":"glass"},"type":"list"},{"data":{"content":"**Connecting to the Master Theorem:**\n\nThe recurrence relation for binary search is:\n\n```\nT(n) = T(n/2) + O(1)\n```\n\nWhere:\n- `T(n)` is the time for a problem of size n\n- `T(n/2)` is the time to solve the one subproblem of size n/2\n- `O(1)` is the work to divide (compute midpoint) and combine (return result)\n\nApplying the Master Theorem:\n- a = 1 (one subproblem)\n- b = 2 (problem size halves)\n- f(n) = O(1) (constant work per level)\n- log_b(a) = log_2(1) = 0\n- f(n) = Θ(n^0) = Θ(1)\n\nThis is Case 2: T(n) = Θ(log n).\n\nThe D&C analysis gives us the same result we know intuitively, but through a principled framework applicable to *any* recursive algorithm."},"type":"text"},{"data":{"icon":"Info","title":"From Intuition to Formalism","content":"Most developers intuit that 'halving repeatedly gives log n steps.' The D&C perspective elevates this intuition to a formal framework with the Master Theorem, enabling analysis of algorithms too complex for intuition alone.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":4},{"id":"binary-search-variants","title":"Binary Search Variants Through the D&C Lens","content":[{"data":{"content":"Once you see binary search as D&C, you can understand its many variants as modifications to the basic pattern. Each variant tweaks the divide, conquer, or combine phase slightly:"},"type":"text"},{"data":{"rows":[["Find First Occurrence","Continue searching left even after finding target","Modified base case + forced left recursion"],["Find Last Occurrence","Continue searching right even after finding target","Modified base case + forced right recursion"],["Find Insertion Point","Return position where element would be inserted","Modified base case returns boundary"],["Search in Rotated Array","Identify which half is sorted before deciding","Modified divide phase uses additional check"],["Binary Search on Answer","Search for answer satisfying a predicate","Modified comparison uses predicate function"],["Ternary Search","Divide into three parts instead of two","Modified divide phase creates two midpoints"]],"caption":"Binary Search Variants in D&C Terms","headers":["Variant","Modification","D&C Impact"]},"type":"table"},{"data":{"fileName":"binary_search_first_occurrence.py","languages":[{"code":"$7d","label":"Python","value":"python"}]},"type":"code"},{"data":{"content":"**The Pattern Remains:**\n\nNotice that all variants maintain the core D&C structure:\n- They all **divide** by computing a midpoint\n- They all **conquer** by recursing into one (or occasionally both) halves\n- They all **combine** by returning results (sometimes tracking additional state)\n\nThe differences lie in the decision logic and what constitutes a 'solution.' Understanding this allows you to derive new variants as needed rather than memorizing each separately."},"type":"text"}],"titleType":"number","titleNumber":5},{"id":"comparative-analysis","title":"Comparative Analysis: Binary Search vs. Other D&C Algorithms","content":[{"data":{"content":"Understanding how binary search compares to other D&C algorithms illuminates the spectrum of the paradigm. Let's compare binary search with merge sort and quick sort—three algorithms that apply D&C differently:"},"type":"text"},{"data":{"rows":[["Subproblems Created","2 (but solve only 1)","2 (solve both)","2 (solve both)"],["Subproblem Size","n/2","n/2 each","Variable (depends on pivot)"],["Divide Complexity","O(1) — just compute mid","O(1) — just compute mid","O(n) — partition around pivot"],["Combine Complexity","O(1) — just return","O(n) — merge two sorted halves","O(1) — just concatenate"],["Total Time","O(log n)","O(n log n)","O(n log n) average"],["Where Work Happens","Decision making (minimal)","Combine phase (merge)","Divide phase (partition)"]],"caption":"D&C Structure Comparison","headers":["Aspect","Binary Search","Merge Sort","Quick Sort"]},"type":"table"},{"data":{"left":[{"data":{"items":["Logarithmic time — extremely fast","Constant space in iterative form","Trivial combine phase","Simple implementation","Easily modified for variants"],"title":{"icon":"CheckCircle","text":"Binary Search Advantages","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}],"right":[{"data":{"items":["Requires sorted input","Only finds single elements","Cannot modify the data","Random access required","Not suitable for streaming data"],"title":{"icon":"AlertCircle","text":"Binary Search Constraints","type":"icon","color":"destructive","variant":"outline-circle"},"variant":"accent"},"type":"list"}]},"type":"two-column"},{"data":{"icon":"Lightbulb","title":"Work Distribution in D&C","content":"An illuminating insight: in merge sort, the 'clever work' happens during COMBINE (merging). In quick sort, it happens during DIVIDE (partitioning). In binary search, the work is minimal at both phases—the intelligence lies in ELIMINATING one subproblem entirely. This makes binary search the most efficient of the three.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":6},{"id":"deeper-principle","title":"The Deeper Principle: Search Space Elimination","content":[{"data":{"content":"Viewing binary search as D&C leads us to an even more fundamental insight: the power of **search space elimination**. This principle extends far beyond sorted arrays.\n\n**The Core Idea:**\n\nMany problems can be framed as searching for something within a space of possibilities. If we can find a way to **eliminate** large portions of this space with minimal work, we can achieve sublinear time complexity.\n\nBinary search eliminates half the search space with each O(1) comparison. This 'elimination rate' is what produces logarithmic complexity.\n\n**Generalizing the Pattern:**\n\nThis principle applies to many scenarios:"},"type":"text"},{"data":{"items":["**Binary Search on Answer Space** — Instead of searching an array, search the space of possible answers. For 'minimum capacity to ship packages in D days,' binary search over capacities.","**Decision Problems** — 'Is it possible to achieve X?' can often be binary searched over the threshold value.","**Optimization** — 'Find the minimum X such that condition holds' is often solvable by binary search if the condition is monotonic.","**Game Theory** — Minimax with alpha-beta pruning eliminates large portions of the game tree.","**Constraint Satisfaction** — Branch-and-bound eliminates branches that cannot improve the current best solution."],"title":{"icon":"Zap","text":"Search Space Elimination Examples","type":"icon","color":"primary","variant":"outline-circle"},"variant":"glass"},"type":"list"},{"data":{"content":"**The Invariant:**\n\nAll search space elimination techniques maintain an invariant: *the solution, if it exists, is contained in the remaining search space*. Binary search maintains:\n\n> If target exists in arr, then arr[left..right] contains it.\n\nEach comparison either finds the target or safely eliminates one half—preserving the invariant while shrinking the space.\n\nThis invariant-based thinking is powerful. When designing algorithms, ask: *What portions of the search space can I safely eliminate? What invariant justifies this elimination?*"},"type":"text"},{"data":{"icon":"AlertCircle","title":"Prerequisite for Elimination","content":"Search space elimination only works when you can determine which portions to eliminate WITHOUT examining them. For binary search, the sorted property provides this. For other problems, you need similar structural properties (monotonicity, ordering, etc.) to enable safe elimination.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":7},{"id":"summary-looking-ahead","title":"Summary and Looking Ahead","content":[{"data":{"content":"We've reexamined binary search through the lens of divide-and-conquer, revealing insights that deepen our understanding of this fundamental algorithm."},"type":"text"},{"data":{"type":"ordered","items":["**Binary search is a D&C algorithm** — It follows the divide-conquer-combine pattern, though with a trivial combine phase.","**It's specifically decrease-and-conquer** — Only one subproblem is solved; the other is eliminated based on a comparison.","**The D&C view enables formal analysis** — The recurrence T(n) = T(n/2) + O(1) yields O(log n) via the Master Theorem.","**Variants are modifications to the D&C pattern** — Find-first, find-last, insertion point all tweak the same underlying structure.","**Search space elimination is the deeper principle** — The sorted property allows safe elimination of half the space per step.","**This perspective generalizes** — Binary search on answer space, decision problems, and optimization all leverage the same insight."],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**What's Next:**\n\nIn the following pages, we'll examine each phase of binary search's D&C structure in detail:\n\n- **Page 2**: The DIVIDE phase — How binary search splits the search space\n- **Page 3**: The CONQUER phase — How binary search recursively solves one subproblem\n- **Page 4**: The COMBINE phase — How binary search returns results (and why it's trivial)\n\nThis deep dive will solidify your understanding and prepare you to recognize and apply the pattern in novel situations."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"You now understand binary search as an instance of the divide-and-conquer paradigm. This perspective elevates the algorithm from a memorized procedure to an application of fundamental principles—principles that extend to countless other problems.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":8}],"isLocked":false},{"id":"seed_3b70672b06ea1b52330da357b36f4996","title":"Divide — Split Search Space","order":1,"content":null,"isLocked":true},{"id":"seed_cd60ec75c78fdc261d420a355035b292","title":"Conquer — Search One Half","order":2,"content":null,"isLocked":true},{"id":"seed_19ae59f15580aaa8893ebacf269597b2","title":"Combine — Return Result","order":3,"content":null,"isLocked":true}]}}