7a:T45e,To truly understand why sorted data is essential, let's examine what happens when we attempt binary search on unsorted data. **Example: Searching for 5 in an Unsorted Array** Consider the array: [7, 2, 9, 5, 1, 8, 3] Using binary search logic: 1. Check middle element (index 3): value is 5 ✓ Found! This seems to work! But that's pure luck. Let's search for 8: 1. Check middle element (index 3): value is 5 2. Since 8 > 5, search right half: [1, 8, 3] 3. Check middle of right half (index 5): value is 8 ✓ Found! Still lucky. Now search for 2: 1. Check middle element (index 3): value is 5 2. Since 2 < 5, search left half: [7, 2, 9] 3. Check middle of left half (index 1): value is 2 ✓ Found! But now search for 3: 1. Check middle element (index 3): value is 5 2. Since 3 < 5, search left half: [7, 2, 9] 3. Check middle of left half (index 1): value is 2 4. Since 3 > 2, search right of index 1: [9] 5. Check: value is 9 ≠ 3 → **TARGET NOT FOUND** But 3 IS in the array (at index 6)! Binary search failed because it made assumptions ("3 must be to the right of 2") that only hold for sorted data.7b:T48b,// Demonstration: Binary search fails on unsorted data function binarySearch(arr: number[], target: number): number { /** Standard binary search (assumes sorted input) */ let left = 0; let right = arr.length - 1; while (left <= right) { const mid = Math.floor((left + right) / 2); if (arr[mid] === target) { return mid; } else if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1; // Not found } // Unsorted array const unsorted = [7, 2, 9, 5, 1, 8, 3]; // Search for 3 (which exists at index 6) let result = binarySearch(unsorted, 3); console.log(`Search for 3: index ${result}`); // Outputs: -1 (wrong!) // Search for 7 (which exists at index 0) result = binarySearch(unsorted, 7); console.log(`Search for 7: index ${result}`); // May output -1 (wrong!) // The same array, but sorted const sortedArr = [...unsorted].sort((a, b) => a - b); // [1, 2, 3, 5, 7, 8, 9] // Now binary search works correctly result = binarySearch(sortedArr, 3); console.log(`Sorted - Search for 3: index ${result}`); // Outputs: 2 (correct!)7c:T48f,from dataclasses import dataclass from typing import List import bisect @dataclass class Student: name: str gpa: float id: int def __lt__(self, other): # Primary sort: by GPA (descending) if self.gpa != other.gpa: return self.gpa > other.gpa # Higher GPA comes first # Secondary sort: by name (ascending) if self.name != other.name: return self.name < other.name # Tertiary sort: by ID (ascending) return self.id < other.id # Creating a sorted list of students students = [ Student("Alice", 3.9, 101), Student("Bob", 3.7, 102), Student("Charlie", 3.9, 103), Student("Diana", 3.5, 104), ] # Sort according to our custom ordering students.sort() # Binary search for a student with GPA 3.7 # Using bisect with a key function (Python 3.10+) target_gpa = 3.7 # Finding position where a student with this GPA would be inserted gpas = [s.gpa for s in sorted(students, key=lambda s: -s.gpa)] position = bisect.bisect_left(gpas, target_gpa, key=lambda x: -x) print(f"Students sorted by custom ordering:") for s in students: print(f" {s.name}: GPA {s.gpa}")7d:T5ad,interface Student { name: string; gpa: number; id: number; } // Custom comparison function for students function compareStudents(a: Student, b: Student): number { // Primary sort: by GPA (descending) if (a.gpa !== b.gpa) { return b.gpa - a.gpa; // Higher GPA comes first } // Secondary sort: by name (ascending) if (a.name !== b.name) { return a.name.localeCompare(b.name); } // Tertiary sort: by ID (ascending) return a.id - b.id; } // Binary search with custom comparator function binarySearchStudentByGPA( students: Student[], targetGPA: number ): number { let left = 0; let right = students.length - 1; while (left <= right) { const mid = Math.floor((left + right) / 2); if (students[mid].gpa === targetGPA) { return mid; } else if (students[mid].gpa > targetGPA) { // Higher GPAs are at the start (descending order) left = mid + 1; } else { right = mid - 1; } } return -1; } // Creating and sorting students const students: Student[] = [ { name: "Alice", gpa: 3.9, id: 101 }, { name: "Bob", gpa: 3.7, id: 102 }, { name: "Charlie", gpa: 3.9, id: 103 }, { name: "Diana", gpa: 3.5, id: 104 }, ]; students.sort(compareStudents); console.log("Students sorted by custom ordering:"); students.forEach(s => console.log(` ${s.name}: GPA ${s.gpa}`));7e:Ta03,from typing import TypeVar, Callable, Sequence import random T = TypeVar('T') def is_sorted( arr: Sequence[T], key: Callable[[T], any] = lambda x: x, reverse: bool = False ) -> bool: """ Verify that a sequence is sorted. Args: arr: Sequence to check key: Function to extract comparison key reverse: True if checking descending order Returns: True if sorted according to criteria Time: O(n), Space: O(1) """ if len(arr) <= 1: return True prev = key(arr[0]) for i in range(1, len(arr)): curr = key(arr[i]) if reverse: if curr > prev: return False else: if curr < prev: return False prev = curr return True def find_sorted_violations( arr: Sequence[T], key: Callable[[T], any] = lambda x: x, reverse: bool = False ) -> list[tuple[int, T, T]]: """ Find all positions where sorted order is violated. Returns: List of (index, element, previous_element) for violations """ violations = [] if len(arr) <= 1: return violations prev = key(arr[0]) for i in range(1, len(arr)): curr = key(arr[i]) violated = (curr > prev) if reverse else (curr < prev) if violated: violations.append((i, arr[i], arr[i-1])) prev = curr return violations def safe_binary_search(arr: Sequence[T], target: T, verify: bool = True) -> int: """ Binary search with optional sortedness verification. In development/testing: verify=True catches bugs early In production: verify=False for performance (after validation) """ if verify and not is_sorted(arr): raise ValueError("Binary search requires sorted input!") 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 # Usage examples sorted_data = [1, 3, 5, 7, 9, 11, 13, 15] unsorted_data = [1, 5, 3, 7, 9, 11, 13, 15] print(f"Sorted check: {is_sorted(sorted_data)}") # True print(f"Unsorted check: {is_sorted(unsorted_data)}") # False violations = find_sorted_violations(unsorted_data) print(f"Violations found: {violations}") # [(2, 3, 5)] try: safe_binary_search(unsorted_data, 7, verify=True) except ValueError as e: print(f"Caught error: {e}")7f:T9e2,function isSorted( arr: T[], compare: (a: T, b: T) => number = (a, b) => (a as any) - (b as any), reverse: boolean = false ): boolean { /** * Verify that an array is sorted. * Time: O(n), Space: O(1) */ if (arr.length <= 1) return true; for (let i = 1; i < arr.length; i++) { const cmp = compare(arr[i-1], arr[i]); if (reverse) { if (cmp < 0) return false; // Should be descending } else { if (cmp > 0) return false; // Should be ascending } } return true; } interface Violation { index: number; element: T; previousElement: T; } function findSortedViolations( arr: T[], compare: (a: T, b: T) => number = (a, b) => (a as any) - (b as any), reverse: boolean = false ): Violation[] { /** * Find all positions where sorted order is violated. */ const violations: Violation[] = []; if (arr.length <= 1) return violations; for (let i = 1; i < arr.length; i++) { const cmp = compare(arr[i-1], arr[i]); const violated = reverse ? (cmp < 0) : (cmp > 0); if (violated) { violations.push({ index: i, element: arr[i], previousElement: arr[i-1] }); } } return violations; } function safeBinarySearch( arr: T[], target: T, verify: boolean = true, compare: (a: T, b: T) => number = (a, b) => (a as any) - (b as any) ): number { /** * Binary search with optional sortedness verification. */ if (verify && !isSorted(arr, compare)) { throw new Error("Binary search requires sorted input!"); } let left = 0; let right = arr.length - 1; while (left <= right) { const mid = Math.floor((left + right) / 2); const cmp = compare(arr[mid], target); if (cmp === 0) return mid; else if (cmp < 0) left = mid + 1; else right = mid - 1; } return -1; } // Usage examples const sortedData = [1, 3, 5, 7, 9, 11, 13, 15]; const unsortedData = [1, 5, 3, 7, 9, 11, 13, 15]; console.log(`Sorted check: ${isSorted(sortedData)}`); // true console.log(`Unsorted check: ${isSorted(unsortedData)}`); // false const violations = findSortedViolations(unsortedData); console.log(`Violations found:`, violations); try { safeBinarySearch(unsortedData, 7, true); } catch (e) { console.log(`Caught error: ${(e as Error).message}`); }72:{"json":{"id":"seed_ac1ce60c5d0417b1415db9875708cb47","slug":"binary-search-core-algorithm","category":"Data Structures & Algorithms","topic":"Binary Search — Core Algorithm","title":"Binary Search — Core Algorithm","description":"Master the binary search algorithm from first principles. Understand why sorted data is essential, learn the divide-and-eliminate strategy, implement both iterative and recursive versions, and develop deep intuition for its O(log n) time complexity.","difficulty":"BEGINNER","estimatedMinutes":75,"pages":[{"id":"seed_d6468c6a55f5df4ae81f22ad8a5e1d63","title":"Prerequisite — Sorted Data","order":0,"content":[{"id":"opening-hook","title":"The Foundation Binary Search Stands On","content":[{"data":{"content":"Before we explore how binary search works, we must understand **why it works**. Binary search isn't magic—it's a logical consequence of one specific property in our data: **order**.\n\nImagine trying to find a word in a dictionary. You don't start at page one and scan every word. Instead, you open the dictionary somewhere in the middle, see if your word comes before or after that point, and eliminate half the remaining pages. You do this instinctively because dictionaries are **alphabetically sorted**.\n\nNow imagine a dictionary where words appear in random order. Every search becomes a nightmare—you'd have to check every single entry. The sorting property that makes dictionaries usable is *precisely* the property that makes binary search possible."},"type":"text"},{"data":{"icon":"Target","title":"What You Will Learn","content":"By the end of this page, you will understand:\n\n• Why sorted data isn't just helpful, but **mathematically essential** for binary search\n• What properties sorted data guarantees and how binary search exploits them\n• The formal definition of sortedness and its implications\n• Common scenarios where this prerequisite is satisfied or must be established\n• The relationship between sorting cost and search efficiency","variant":"info"},"type":"callout"}]},{"id":"understanding-sortedness","title":"Understanding Sortedness: A Formal Definition","content":[{"data":{"content":"Before we can appreciate why sorted data enables binary search, we must precisely define what it means for data to be sorted.\n\n**Formal Definition:**\n\nA sequence A = [a₀, a₁, a₂, ..., aₙ₋₁] is said to be **sorted in ascending order** if and only if:\n\n> For all indices i and j where 0 ≤ i < j < n, we have aᵢ ≤ aⱼ\n\nEquivalently, for consecutive elements:\n\n> For all i where 0 ≤ i < n-1, we have aᵢ ≤ aᵢ₊₁\n\nThis seemingly simple property—that every element is less than or equal to the one following it—has profound implications that binary search exploits."},"type":"text"},{"data":{"icon":"Info","title":"Strict vs. Non-Strict Ordering","content":"We use ≤ (less than or equal) rather than < (strictly less than) to allow **duplicate values**. A sorted array can contain repeated elements: [1, 2, 2, 3, 5, 5, 5, 8] is perfectly valid sorted data. This distinction becomes critical when we later discuss finding first/last occurrences of a target value.","variant":"note"},"type":"callout"},{"data":{"content":"**Descending Order:**\n\nAn array sorted in descending order reverses the inequality:\n\n> For all i where 0 ≤ i < n-1, we have aᵢ ≥ aᵢ₊₁\n\nBinary search works identically on descending-sorted arrays—we simply reverse our elimination logic. When the midpoint value is greater than our target, we search right (not left).\n\n**The Transitivity Property:**\n\nSortedness guarantees **transitivity**: if we know a₃ < a₇, and the array is sorted, we can immediately conclude:\n\n- All elements a₀, a₁, a₂, a₃ are ≤ a₃ < a₇\n- All elements a₇, a₈, ..., aₙ₋₁ are ≥ a₇ > a₃\n\nThis transitivity is the mathematical foundation of binary search. By examining a single element, we gain information about **all elements on either side** of it."},"type":"text"}],"titleType":"number","titleNumber":1},{"id":"order-invariant","title":"The Order Invariant: What Sortedness Guarantees","content":[{"data":{"content":"Sortedness establishes what we call the **order invariant**—a property that holds at every position in the array and enables logical deduction about element locations.\n\n**The Key Insight:**\n\nIn a sorted array, if we're searching for a target value T and we examine any element at position mid with value M:\n\n1. **If M < T**: The target *cannot* exist at indices 0 through mid (if it exists at all). Why? Because all elements before mid are ≤ M, and M < T, so all elements before mid are < T.\n\n2. **If M > T**: The target *cannot* exist at indices mid through n-1. All elements after mid are ≥ M > T, so they're all too large.\n\n3. **If M = T**: We've found the target (or one instance of it).\n\nThis is the order invariant in action: **a single comparison gives us information about half the array**."},"type":"text"},{"data":{"rows":[["M < Target","Target cannot be in left half (indices 0 to mid)","No information about other elements"],["M > Target","Target cannot be in right half (indices mid to n-1)","No information about other elements"],["M = Target","Found target (may be duplicates elsewhere)","Found target (may be duplicates elsewhere)"],["Information per comparison","Eliminates ~50% of remaining elements","Eliminates exactly 1 element"]],"caption":"Information Gained from a Single Comparison in Sorted vs. Unsorted Data","headers":["Comparison Result","Sorted Array","Unsorted Array"]},"type":"table"},{"data":{"content":"**The Power of Elimination:**\n\nThe table above reveals something profound: in sorted data, each comparison eliminates roughly **half** of the remaining search space. In unsorted data, each comparison only tells us about the specific element we examined—providing no information about unexamined elements.\n\nThis is why binary search achieves O(log n) complexity: we halve the problem with each step. After k comparisons, we've reduced the search space to n/2ᵏ elements. In unsorted data, after k comparisons, we still have n - k elements (linear reduction)."},"type":"text"},{"data":{"icon":"Lightbulb","title":"Visualizing the Invariant","content":"Think of a sorted array as a number line where values increase left-to-right. Any vertical line (representing a position) divides all values into two groups: 'less than or equal' on the left, 'greater than or equal' on the right. Binary search exploits this partition to navigate toward the target.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":2},{"id":"unsorted-breaks-binary-search","title":"Why Unsorted Data Breaks Binary Search","content":[{"data":{"content":"$7a"},"type":"text"},{"data":{"icon":"AlertCircle","title":"The Fundamental Problem","content":"In unsorted data, seeing that M < Target tells us **nothing** about where Target might be. It could be anywhere—left, right, or not present at all. The logical deduction that powers binary search becomes invalid, and the algorithm produces incorrect results.","variant":"error"},"type":"callout"},{"data":{"content":"**Formal Proof by Counterexample:**\n\nFor any unsorted array of n elements (n ≥ 3), we can always construct a scenario where binary search fails:\n\n1. Let the middle element have value M\n2. Place a target value T where T > M but in the left half\n3. Binary search will look in the right half and miss the target\n\nSince this counterexample exists for every unsorted array, binary search is guaranteed to be unreliable without sorted data. Not \"often wrong\"—**provably incorrect**."},"type":"text"},{"data":{"fileName":"unsorted_failure_demo.py","languages":[{"code":"# Demonstration: Binary search fails on unsorted data\n\ndef binary_search(arr, target):\n \"\"\"Standard binary search (assumes sorted input)\"\"\"\n left, right = 0, len(arr) - 1\n \n while left <= right:\n mid = (left + right) // 2\n if arr[mid] == target:\n return mid\n elif arr[mid] < target:\n left = mid + 1\n else:\n right = mid - 1\n \n return -1 # Not found\n\n# Unsorted array\nunsorted = [7, 2, 9, 5, 1, 8, 3]\n\n# Search for 3 (which exists at index 6)\nresult = binary_search(unsorted, 3)\nprint(f\"Search for 3: index {result}\") # Outputs: -1 (wrong!)\n\n# Search for 7 (which exists at index 0)\nresult = binary_search(unsorted, 7)\nprint(f\"Search for 7: index {result}\") # May output -1 (wrong!)\n\n# The same array, but sorted\nsorted_arr = sorted(unsorted) # [1, 2, 3, 5, 7, 8, 9]\n\n# Now binary search works correctly\nresult = binary_search(sorted_arr, 3)\nprint(f\"Sorted - Search for 3: index {result}\") # Outputs: 2 (correct!)","label":"Python","value":"python"},{"code":"$7b","label":"TypeScript","value":"typescript"}]},"type":"code"}],"titleType":"number","titleNumber":3},{"id":"sources-of-sorted-data","title":"Sources of Sorted Data in Practice","content":[{"data":{"content":"Understanding when data arrives already sorted—and when we must sort it ourselves—is crucial for effective algorithm selection.\n\n**Naturally Sorted Data:**\n\nSome data sources inherently produce sorted data:"},"type":"text"},{"data":{"items":["**Time-series data** — Logs, events, and measurements recorded chronologically are sorted by timestamp by construction.","**Database indices** — B-trees and similar structures store keys in sorted order, enabling range queries and binary search.","**Merge results** — The output of merge operations (as in merge sort) is sorted if inputs were sorted.","**Priority queue extractions** — Extracting all elements from a min-heap produces ascending order.","**Lexicographic enumerations** — Algorithms generating permutations or combinations often produce sorted output.","**Sorted insertions** — Data structures like balanced BSTs maintain sorted order as elements are added."],"title":{"icon":"CheckCircle","text":"Common Sources of Pre-Sorted Data","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**Data Requiring Explicit Sorting:**\n\nMost real-world data is not naturally sorted. User inputs, API responses, file contents, and random samples all arrive in arbitrary order. To use binary search, we must first apply a sorting algorithm.\n\n**The Sorting Investment:**\n\nHere's where strategic thinking becomes essential. Sorting takes O(n log n) time for comparison-based sorts. If we're only searching once, spending O(n log n) to enable O(log n) search is worse than just using O(n) linear search!\n\nThe calculus changes when we search **repeatedly**:"},"type":"text"},{"data":{"rows":[["1","O(n)","O(n log n) + O(log n) ≈ O(n log n)","Linear Search"],["log n","O(n log n)","O(n log n) + O(log² n) ≈ O(n log n)","Approximately Equal"],["n","O(n²)","O(n log n) + O(n log n) = O(n log n)","Binary Search (by n/log n factor)"],["n²","O(n³)","O(n log n) + O(n² log n) = O(n² log n)","Binary Search (by n/log n factor)"]],"caption":"Break-Even Analysis: Sorting + Binary Search vs. Repeated Linear Search","headers":["Searches (k)","Linear Search Total","Sort Once + Binary Search","Winner"]},"type":"table"},{"data":{"icon":"Lightbulb","title":"The Rule of Thumb","content":"If you'll search the same data more than **log n** times, sorting first and using binary search is more efficient than repeated linear searches. For n = 1,000,000, that's about 20 searches. For n = 1 billion, it's about 30. In practice, most applications perform thousands or millions of searches on the same data, making the sorting investment highly worthwhile.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":4},{"id":"maintaining-sorted-order","title":"Maintaining Sorted Order with Dynamic Data","content":[{"data":{"content":"Real systems often face a challenge: data changes over time. Elements are inserted, deleted, or modified. How do we maintain sorted order efficiently?\n\n**Option 1: Re-Sort After Each Modification**\n\nThe simplest approach—run a full sort after any change—is often impractical. For n = 1,000,000 elements, each modification triggers O(n log n) ≈ 20 million operations.\n\n**Option 2: Insertion at Correct Position**\n\nWhen inserting into a sorted array:\n1. Use binary search to find the correct insertion position: O(log n)\n2. Shift all subsequent elements to make room: O(n)\n3. Insert the new element: O(1)\n\nTotal: O(n) per insertion. Better than re-sorting, but still expensive for frequent insertions.\n\n**Option 3: Sorted Data Structures**\n\nFor truly dynamic data, specialized structures maintain sorted order efficiently:"},"type":"text"},{"data":{"items":["**Balanced BSTs (AVL, Red-Black)** — O(log n) insert, delete, and search. In-order traversal yields sorted sequence.","**Skip Lists** — Probabilistic structure with O(log n) expected operations. Used in Redis and LevelDB.","**B-Trees / B+ Trees** — Optimized for disk access with O(log n) operations. Foundation of database indexing.","**Sorted Sets (e.g., Java TreeSet, C++ std::set)** — Library implementations of balanced BSTs."],"title":{"icon":"Zap","text":"Data Structures for Dynamic Sorted Data","type":"icon","color":"primary","variant":"outline-circle"},"variant":"glass"},"type":"list"},{"data":{"content":"**The Trade-off Triangle:**\n\nChoosing a data representation involves balancing:\n\n1. **Search efficiency** — Arrays with binary search: O(log n), optimal\n2. **Modification efficiency** — BSTs: O(log n), arrays: O(n)\n3. **Memory efficiency** — Arrays: minimal overhead, BSTs: pointer overhead per node\n\nFor read-heavy workloads (many searches, few modifications), sorted arrays with binary search are ideal. For write-heavy workloads, balanced trees or other dynamic structures are preferred.\n\n**Batch Operations:**\n\nA common optimization for mixed workloads: buffer modifications, then periodically rebuild. For example:\n- Accept new elements into an unsorted buffer\n- When buffer reaches threshold, sort and merge into main array\n- Search both locations (main array + buffer)\n\nThis amortizes the sorting cost across multiple insertions, achieving better average-case performance."},"type":"text"},{"data":{"icon":"Info","title":"The Real-World Balance","content":"Production systems often use hybrid approaches. A database might use a B-tree for the live index (supporting efficient updates) but periodically compact data into sorted runs for optimal read performance. Understanding sorted data's role in binary search helps you appreciate these architectural decisions.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":5},{"id":"beyond-numerical-ordering","title":"Beyond Numerical Ordering: Comparison Functions","content":[{"data":{"content":"Binary search works whenever data has a **total ordering**—a consistent way to compare any two elements. This extends far beyond numbers.\n\n**Requirements for a Valid Comparison:**\n\nA comparison function must satisfy three properties:\n\n1. **Antisymmetry**: If a ≤ b and b ≤ a, then a = b\n2. **Transitivity**: If a ≤ b and b ≤ c, then a ≤ c\n3. **Totality**: For any a and b, either a ≤ b or b ≤ a (or both)\n\nAny comparison satisfying these properties enables binary search."},"type":"text"},{"data":{"fileName":"custom_comparison.py","languages":[{"code":"$7c","label":"Python","value":"python"},{"code":"$7d","label":"TypeScript","value":"typescript"}]},"type":"code"},{"data":{"content":"**Common Orderings in Practice:**\n\n- **Lexicographic (strings)**: \"apple\" < \"banana\" < \"cherry\"\n- **Chronological (dates/times)**: Earlier < Later\n- **Hierarchical (versions)**: \"2.1.3\" < \"2.2.0\" < \"2.10.1\" (requires semantic parsing)\n- **Custom business rules**: Priority levels, urgency rankings\n\n**The Critical Constraint:**\n\nWhatever comparison you use for sorting, you **must use the same comparison** for binary search. Sorting by one criterion and searching by another produces incorrect results—the order invariant only holds for the specific comparison used to establish order."},"type":"text"},{"data":{"icon":"AlertCircle","title":"Consistency is Non-Negotiable","content":"A common bug: sorting a list of (key, value) pairs by key, then binary searching by value. This fails silently—the element may exist but won't be found because the order invariant applies to keys, not values. Always verify that your search criterion matches your sort criterion.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":6},{"id":"verifying-sortedness","title":"Verifying Sortedness: Defensive Programming","content":[{"data":{"content":"In production code, trusting that input is sorted can lead to subtle, hard-to-diagnose bugs. Binary search on unsorted data doesn't crash—it returns wrong answers silently.\n\n**When to Verify:**\n\n- Data received from external sources (APIs, user uploads, files)\n- Data processed through pipelines where sorting might be lost\n- After modifications that could disrupt order\n- During debugging of mysterious search failures"},"type":"text"},{"data":{"fileName":"verify_sorted.py","languages":[{"code":"$7e","label":"Python","value":"python"},{"code":"$7f","label":"TypeScript","value":"typescript"}]},"type":"code"},{"data":{"icon":"Lightbulb","title":"Debug Mode vs. Production","content":"Verification costs O(n)—the same as linear search. Enable it during development and testing to catch bugs early, but disable it in performance-critical production paths (after you've validated your data pipeline ensures sortedness).","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":7},{"id":"summary","title":"Summary: The Sorted Data Contract","content":[{"data":{"content":"Sorted data isn't just a nice-to-have for binary search—it's the mathematical foundation that makes the algorithm correct. Without order, we cannot make deductions; without deductions, we cannot eliminate half the search space; without elimination, we cannot achieve logarithmic efficiency.\n\nLet's consolidate what we've learned:"},"type":"text"},{"data":{"type":"ordered","items":["**The Order Invariant** — Sorted data guarantees that examining one element tells us about all elements to its left and right. This is the foundation of binary search's power.","**Unsorted Data Breaks Everything** — Binary search on unsorted data doesn't just perform poorly—it produces incorrect results. The algorithm's correctness proof depends on sortedness.","**The Sorting Investment** — Sorting costs O(n log n), but enables O(log n) searches. For repeated searches, this investment pays enormous dividends.","**Dynamic Data Requires Care** — Maintaining sorted order amid insertions and deletions requires either O(n) array shifts or specialized data structures like balanced trees.","**Comparison Consistency** — Any total ordering works, but you must use the same comparison for sorting and searching. Mixing criteria produces silent failures.","**Verify When Uncertain** — In defensive programming, validate sortedness when data sources are untrusted or pipelines are complex."],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**What's Next:**\n\nNow that we understand *why* sorted data is essential, we're ready to explore *how* binary search exploits this property. The next page introduces the **divide-and-eliminate strategy**—the elegant approach that transforms the order invariant into logarithmic efficiency."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"You now understand the essential prerequisite for binary search: sorted data. This isn't merely a requirement to memorize—it's the deep mathematical reason the algorithm works at all. With this foundation, you're ready to learn the divide-and-eliminate strategy that makes binary search one of the most elegant algorithms in computer science.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":8}],"isLocked":false},{"id":"seed_696cbd8084785ad881d91a6d54ada2a1","title":"The Divide-and-Eliminate Strategy","order":1,"content":null,"isLocked":true},{"id":"seed_69d9dda4e0ce40b7d1b11ba80f1debc2","title":"Algorithmic Steps — Iterative and Recursive","order":2,"content":null,"isLocked":true},{"id":"seed_6573ab4638fb00619216b77cd193b93a","title":"Time Complexity — O(log n)","order":3,"content":null,"isLocked":true}]}}