46:"/_next/static/chunks/33yus346z0l_n.js" 47:"/_next/static/chunks/1r8ezocsukqp8.js" 48:"/_next/static/chunks/0iv56yrji_20j.js" 49:"/_next/static/chunks/0wa9m1-tphf9u.js" 4a:"/_next/static/chunks/08cuqqn_f60pp.js" 4b:"/_next/static/chunks/3zdsl3f9b0--r.js" 4c:"/_next/static/chunks/2j22cxchii_xx.js" 4d:"/_next/static/chunks/3bgoyiso1rhn7.js" 4e:"/_next/static/chunks/01a-3hvnqu8wl.js" 4f:"/_next/static/chunks/3m1xjj5kw5fie.js" 50:"/_next/static/chunks/0om3fkgfnicab.js" 51:"/_next/static/chunks/0gafyzg9j9yqj.js" 52:"/_next/static/chunks/20w4eaqlekefm.js" 53:"/_next/static/chunks/449--h5z1s6nq.js" 54:"/_next/static/chunks/3k2gyg36fnag_.js" 55:"/_next/static/chunks/18ggtgz2yf759.js" 56:"/_next/static/chunks/0hlb44ca7-4a2.js" 57:"/_next/static/chunks/253gnmj0-cj17.js" 58:"/_next/static/chunks/09nq57stwzkgf.js" 59:"/_next/static/chunks/082jo-0ajazgr.js" 5a:"/_next/static/chunks/2ozcrjb_hh74t.js" 5b:"/_next/static/chunks/05i8en-x14ibi.js" 5c:"/_next/static/chunks/32izpn90gvm22.js" 5d:"/_next/static/chunks/0jbzid2v9xv3h.js" 5e:"/_next/static/chunks/0i3-eynrkvqi7.js" 5f:"/_next/static/chunks/1tn-0fivsxsv1.js" 60:"/_next/static/chunks/34h36hyf_ggow.js" 61:"/_next/static/chunks/20329i6m_04t6.js" 62:"/_next/static/chunks/161uxd62cjny2.js" 63:"/_next/static/chunks/2k8pepwc4pxns.js" 64:I[593304,["$2b","$2c","$2d","$2e","$2f","$30","$46","$47","$48","$49","$4a","$4b","$4c","$4d","$4e","$4f","$50","$51","$52","$53","$54","$55","$56","$57","$58","$59","$5a","$5b","$5c","$5d","$5e","$5f","$60","$61","$62","$63"],"OwnedHydration"] 65:T85b,def identify_sorted_half(arr, low, high): """ Identifies which half of a rotated sorted array is sorted. Returns: 'left' if the left half [low..mid] is sorted 'right' if the right half [mid..high] is sorted 'both' if the entire range is sorted (no rotation in this range) """ if low >= high: return 'both' # Single element or empty mid = (low + high) // 2 # Check if left half is sorted left_sorted = arr[low] <= arr[mid] # Check if right half is sorted right_sorted = arr[mid] <= arr[high] if left_sorted and right_sorted: return 'both' # Entire range is sorted elif left_sorted: return 'left' else: return 'right' # Demonstration def visualize_sorted_half(arr): """Visualizes which half is sorted at each binary search step.""" low, high = 0, len(arr) - 1 step = 0 print(f"Array: {arr}") print("-" * 50) while low <= high: mid = (low + high) // 2 result = identify_sorted_half(arr, low, high) left_half = arr[low:mid+1] right_half = arr[mid:high+1] print(f"Step {step}:") print(f" Range: [{low}, {high}], mid = {mid}") print(f" Left half: {left_half} {'✓ SORTED' if result in ['left', 'both'] else ''}") print(f" Right half: {right_half} {'✓ SORTED' if result in ['right', 'both'] else ''}") print(f" arr[low]={arr[low]}, arr[mid]={arr[mid]}, arr[high]={arr[high]}") print() # For demonstration, just shrink range if result == 'left': high = mid - 1 else: low = mid + 1 step += 1 if step > 5: break # Test with different rotations print("=" * 60) print("Example 1: Rotation point in middle-right") visualize_sorted_half([4, 5, 6, 7, 1, 2, 3]) print("=" * 60) print("Example 2: Rotation point in middle-left") visualize_sorted_half([6, 7, 1, 2, 3, 4, 5]) print("=" * 60) print("Example 3: No rotation (fully sorted)") visualize_sorted_half([1, 2, 3, 4, 5, 6, 7])66:Ta03,function identifySortedHalf( arr: number[], low: number, high: number ): 'left' | 'right' | 'both' { /** * Identifies which half of a rotated sorted array is sorted. * * Returns: * 'left' if the left half [low..mid] is sorted * 'right' if the right half [mid..high] is sorted * 'both' if the entire range is sorted */ if (low >= high) { return 'both'; // Single element or empty } const mid = Math.floor((low + high) / 2); // Check if left half is sorted const leftSorted = arr[low] <= arr[mid]; // Check if right half is sorted const rightSorted = arr[mid] <= arr[high]; if (leftSorted && rightSorted) { return 'both'; // Entire range is sorted } else if (leftSorted) { return 'left'; } else { return 'right'; } } function visualizeSortedHalf(arr: number[]): void { /** * Visualizes which half is sorted at each binary search step. */ let low = 0; let high = arr.length - 1; let step = 0; console.log(`Array: [${arr.join(', ')}]`); console.log('-'.repeat(50)); while (low <= high && step <= 5) { const mid = Math.floor((low + high) / 2); const result = identifySortedHalf(arr, low, high); const leftHalf = arr.slice(low, mid + 1); const rightHalf = arr.slice(mid, high + 1); console.log(`Step ${step}:`); console.log(` Range: [${low}, ${high}], mid = ${mid}`); console.log(` Left half: [${leftHalf.join(', ')}] ${ result === 'left' || result === 'both' ? '✓ SORTED' : '' }`); console.log(` Right half: [${rightHalf.join(', ')}] ${ result === 'right' || result === 'both' ? '✓ SORTED' : '' }`); console.log(` arr[low]=${arr[low]}, arr[mid]=${arr[mid]}, arr[high]=${arr[high]}`); console.log(); // For demonstration, just shrink range if (result === 'left') { high = mid - 1; } else { low = mid + 1; } step++; } } // Test with different rotations console.log('='.repeat(60)); console.log('Example 1: Rotation point in middle-right'); visualizeSortedHalf([4, 5, 6, 7, 1, 2, 3]); console.log('='.repeat(60)); console.log('Example 2: Rotation point in middle-left'); visualizeSortedHalf([6, 7, 1, 2, 3, 4, 5]); console.log('='.repeat(60)); console.log('Example 3: No rotation (fully sorted)'); visualizeSortedHalf([1, 2, 3, 4, 5, 6, 7]);67:T6ac,def test_sorted_half_identification(): """Comprehensive test cases for sorted half identification.""" test_cases = [ # (array, expected_sorted_half_at_first_iteration) ([5], "both"), # Single element ([2, 1], "left"), # Two elements, rotated ([1, 2], "both"), # Two elements, not rotated ([3, 4, 5, 1, 2], "left"), # Minimum at position after mid ([5, 1, 2, 3, 4], "right"), # Minimum at position 1 ([1, 2, 3, 4, 5], "both"), # Not rotated ([4, 5, 6, 7, 0, 1, 2], "left"), # Classic LeetCode example ([2, 1], "left"), # Wwo elements rotated once ([11, 13, 15, 17], "both"), # Not rotated, all ascending ([2, 3, 4, 5, 1], "left"), # Rotation at last position ] print("Testing Sorted Half Identification") print("=" * 60) for i, (arr, expected) in enumerate(test_cases): low, high = 0, len(arr) - 1 mid = (low + high) // 2 left_sorted = arr[low] <= arr[mid] right_sorted = arr[mid] <= arr[high] if left_sorted and right_sorted: result = "both" elif left_sorted: result = "left" else: result = "right" status = "✓ PASS" if result == expected else "✗ FAIL" print(f"Test {i+1}: {arr}") print(f" arr[{low}]={arr[low]}, arr[{mid}]={arr[mid]}, arr[{high}]={arr[high]}") print(f" Expected: {expected}, Got: {result} {status}") print() test_sorted_half_identification()45:["$","$L64",null,{"owner":"anonymous","state":{"mutations":[],"queries":[{"dehydratedAt":1792316336656,"state":{"data":{"json":{"id":"seed_0844cd36921eeb829425a91ddb53f42d","slug":"search-in-rotated-arrays","category":"Data Structures & Algorithms","topic":"Search in Rotated Arrays","title":"Search in Rotated Arrays","description":"Master the art of searching in rotated sorted arrays—a classic interview problem that tests your understanding of binary search invariants. Learn to identify sorted portions, adapt the binary search strategy, handle duplicates, and analyze edge cases with surgical precision.","difficulty":"INTERMEDIATE","estimatedMinutes":60,"pages":[{"id":"seed_fbdfda811d61a7a26dc606c968145d75","title":"Identifying the Sorted Portion","order":0,"content":[{"id":"opening-hook","title":"The Rotated Array Challenge","content":[{"data":{"content":"Imagine you're given a sorted array that has been **rotated** at some unknown pivot point. What was once `[1, 2, 3, 4, 5, 6, 7]` might now be `[4, 5, 6, 7, 1, 2, 3]`. The array is still \"mostly sorted\"—but standard binary search would fail catastrophically.\n\nThis is one of the most celebrated problems in algorithm interviews: it appears constantly at Google, Amazon, Meta, and virtually every top tech company. It tests not just whether you know binary search, but whether you *understand* it deeply enough to adapt it to a twisted scenario.\n\nThe key insight that unlocks this entire problem class is deceptively simple: **in any rotated sorted array, at least one half is always perfectly sorted**. Once you internalize this observation, the problem transforms from bewildering to tractable."},"type":"text"},{"data":{"icon":"Target","title":"What You Will Learn","content":"By the end of this page, you will understand the fundamental structure of rotated arrays, why one half is always sorted, and how to identify which half is the sorted portion using a simple O(1) check. This insight is the foundation for all rotated array search strategies.","variant":"info"},"type":"callout"}]},{"id":"what-is-rotated-array","title":"What Is a Rotated Sorted Array?","content":[{"data":{"content":"A **rotated sorted array** is a sorted array that has been pivoted around some index. Think of it like taking a sorted deck of cards, cutting the deck somewhere in the middle, and placing the bottom portion on top.\n\n**Formal definition:**\n\nGiven a sorted array `A` of `n` distinct elements, rotating it by `k` positions produces an array where:\n- Elements `A[k], A[k+1], ..., A[n-1]` appear first (in order)\n- Elements `A[0], A[1], ..., A[k-1]` appear after (in order)\n\nThe rotation \"wraps around\" the array, creating exactly **two sorted subsequences**."},"type":"text"},{"data":{"input":"Original sorted array: [1, 2, 3, 4, 5, 6, 7]","title":"Visualizing Array Rotation","output":"Rotation k=0: [1, 2, 3, 4, 5, 6, 7] — No rotation (still fully sorted)\nRotation k=1: [7, 1, 2, 3, 4, 5, 6] — Last element moves to front\nRotation k=2: [6, 7, 1, 2, 3, 4, 5] — Last two elements move to front\nRotation k=3: [5, 6, 7, 1, 2, 3, 4] — Last three elements move to front\nRotation k=4: [4, 5, 6, 7, 1, 2, 3] — Classic example from most textbooks\nRotation k=7: [1, 2, 3, 4, 5, 6, 7] — Full rotation = back to original","description":"Let's trace through several rotations of the same sorted array to build intuition.","explanation":"Notice that each rotated array contains exactly two sorted runs. The 'break point' is where the larger value is followed by a smaller value—this is the rotation point."},"type":"example"},{"data":{"icon":"Info","title":"The Rotation Point","content":"The **rotation point** (also called the **pivot**) is the index where the rotation occurred. It's the location where arr[i] > arr[i+1], creating a 'cliff' in the otherwise ascending sequence. In `[4, 5, 6, 7, 1, 2, 3]`, the rotation point is at index 3 (value 7), because 7 > 1.","variant":"note"},"type":"callout"},{"data":{"content":"**Real-world interpretation:**\n\nRotated arrays appear in practice more often than you might expect:\n\n1. **Circular buffers** — Log systems often use circular buffers where the 'start' wraps around\n2. **Scheduling systems** — Task queues that rotate based on priority or time\n3. **Database indexing** — Some B-tree variants handle wrap-around ranges\n4. **Financial data** — Rolling windows of time-series data that 'rotate' daily\n\nThe core challenge is that you can't immediately apply binary search because the normal assumption (arr[low] ≤ arr[high]) no longer holds across the entire array."},"type":"text"}],"titleType":"number","titleNumber":1},{"id":"key-observation","title":"The Key Observation — One Half Is Always Sorted","content":[{"data":{"content":"Here is the critical insight that transforms rotated array search from impossible to elegant:\n\n> **In any rotated sorted array divided at its midpoint, at least one of the two halves is guaranteed to be perfectly sorted.**\n\nThis is not a heuristic or approximation—it's a mathematical certainty. Understanding *why* this holds is essential for internalizing the algorithm."},"type":"text"},{"data":{"icon":"Lightbulb","title":"The Fundamental Invariant","content":"Because a rotated sorted array contains exactly two sorted runs, and these runs are contiguous, the rotation point can only be in one half at a time. The half without the rotation point is completely sorted. The half with the rotation point contains elements from both sorted runs, but is 'broken' by the pivot.","variant":"tip"},"type":"callout"},{"data":{"content":"**Rigorous proof:**\n\nLet the array have `n` elements with rotation point at index `p`. When we compute `mid = (low + high) / 2`:\n\n**Case 1: The rotation point `p` is in the right half (p > mid)**\n- The left half `[low..mid]` contains only elements from the second sorted run\n- Since these elements were contiguous in the original sorted array, they remain sorted\n- Therefore: **left half is sorted**\n\n**Case 2: The rotation point `p` is in the left half (p ≤ mid)**\n- The right half `[mid..high]` contains only elements from the first sorted run (post-rotation)\n- These elements were also contiguous in the original sorted array\n- Therefore: **right half is sorted**\n\n**Case 3: The array is not actually rotated (or rotated n times)**\n- The entire array is sorted, meaning **both halves are sorted**\n\nIn all cases, at least one half is sorted. This is the invariant we exploit."},"type":"text"},{"data":{"height":"450px","mermaidSyntax":"flowchart TD\n A[\"Array: [4, 5, 6, 7, 1, 2, 3]\"] --> B[\"mid = 3 (value = 7)\"]\n B --> C{\"Where is rotation point?\"}\n C --> |\"p = 3 (at mid)\"| D[\"Rotation point AT mid\"]\n D --> E[\"Left: [4,5,6,7] ✓ Sorted\"]\n D --> F[\"Right: [7,1,2,3] ✗ Contains pivot\"]\n \n A2[\"Array: [6, 7, 1, 2, 3, 4, 5]\"] --> B2[\"mid = 3 (value = 2)\"]\n B2 --> C2{\"Where is rotation point?\"}\n C2 --> |\"p = 1 (in left half)\"| D2[\"Rotation point in LEFT\"]\n D2 --> E2[\"Left: [6,7,1,2] ✗ Contains pivot\"]\n D2 --> F2[\"Right: [2,3,4,5] ✓ Sorted\"]"},"type":"mermaid-excalidraw"}],"titleType":"number","titleNumber":2},{"id":"how-to-identify-sorted-half","title":"How to Identify the Sorted Half","content":[{"data":{"content":"Now that we know one half is always sorted, how do we determine *which* half? The answer is remarkably simple—we only need to compare the first and middle elements.\n\n**The identification rule:**"},"type":"text"},{"data":{"items":["**If arr[low] ≤ arr[mid]:** The LEFT half `[low..mid]` is sorted. This is because in a sorted sequence, the first element must be ≤ the middle element.","**If arr[low] > arr[mid]:** The RIGHT half `[mid..high]` is sorted. The left half contains the rotation point, so the right half must be the clean sorted portion."],"title":{"icon":"Target","text":"Sorted Half Detection Rules","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"icon":"AlertCircle","title":"Why arr[low] ≤ arr[mid], Not arr[low] < arr[mid]?","content":"We use `≤` (less than or equal) rather than `<` (strictly less than) to handle the edge case where low = mid (when the subarray has only 1-2 elements). In this case, arr[low] = arr[mid], and the 'left half' (just one element) is trivially sorted.","variant":"warning"},"type":"callout"},{"data":{"content":"**Walking through the logic:**\n\nConsider `arr = [4, 5, 6, 7, 1, 2, 3]` with `low = 0`, `high = 6`, `mid = 3`:\n\n1. Check: Is `arr[0]` ≤ `arr[3]`? Is `4 ≤ 7`? **Yes**\n2. Therefore: Left half `[4, 5, 6, 7]` is sorted\n3. This tells us: If our target is ≥ 4 AND ≤ 7, search left; otherwise search right\n\nNow consider `arr = [5, 6, 7, 1, 2, 3, 4]` with `low = 0`, `high = 6`, `mid = 3`:\n\n1. Check: Is `arr[0]` ≤ `arr[3]`? Is `5 ≤ 1`? **No**\n2. Therefore: Right half `[1, 2, 3, 4]` is sorted\n3. This tells us: If our target is ≥ 1 AND ≤ 4, search right; otherwise search left"},"type":"text"},{"data":{"fileName":"identify_sorted_half.py","languages":[{"code":"$65","label":"Python","value":"python"},{"code":"$66","label":"TypeScript","value":"typescript"}],"showLineNumbers":true},"type":"code"}],"titleType":"number","titleNumber":3},{"id":"visual-analysis","title":"Visual Analysis of Rotation Scenarios","content":[{"data":{"content":"To truly internalize this concept, let's systematically analyze all possible rotation positions and see exactly which half ends up sorted. Understanding these patterns will make the algorithm feel intuitive rather than memorized."},"type":"text"},{"data":{"rows":[["k=0","[1, 2, 3, 4, 5, 6, 7]","None","1 ≤ 4 ✓","Both (no rotation)"],["k=1","[7, 1, 2, 3, 4, 5, 6]","0","7 > 3","Right: [3,4,5,6]"],["k=2","[6, 7, 1, 2, 3, 4, 5]","1","6 > 2","Right: [2,3,4,5]"],["k=3","[5, 6, 7, 1, 2, 3, 4]","2","5 > 1","Right: [1,2,3,4]"],["k=4","[4, 5, 6, 7, 1, 2, 3]","3","4 ≤ 7 ✓","Left: [4,5,6,7]"],["k=5","[3, 4, 5, 6, 7, 1, 2]","4","3 ≤ 6 ✓","Left: [3,4,5,6]"],["k=6","[2, 3, 4, 5, 6, 7, 1]","5","2 ≤ 5 ✓","Left: [2,3,4,5]"]],"caption":"Rotation Scenarios for Array [1, 2, 3, 4, 5, 6, 7]","headers":["Rotation","Resulting Array","Pivot Index","arr[0] vs arr[3]","Sorted Half"]},"type":"table"},{"data":{"content":"**Pattern observation:**\n\nLooking at the table, notice that:\n\n1. **When the pivot is in indices 0-2** (left half): The right half is sorted, and `arr[0] > arr[mid]`\n2. **When the pivot is in indices 3-5** (right half): The left half is sorted, and `arr[0] ≤ arr[mid]`\n3. **When there's no pivot** (k=0): Both conditions pass, both halves are sorted\n\nThis is precisely why our single comparison `arr[low] ≤ arr[mid]` works: it detects whether the rotation point has 'polluted' the left half."},"type":"text"},{"data":{"icon":"Lightbulb","title":"Intuitive Way to Remember","content":"Think of it this way: In a normal sorted array, the first element is always ≤ the middle element. If arr[low] > arr[mid], something is 'wrong' with the left half—it contains the pivot where values jump from high back to low. So the right half must be the 'clean' sorted portion.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":4},{"id":"edge-cases","title":"Edge Cases in Sorted Half Identification","content":[{"data":{"content":"Real interview code must handle edge cases flawlessly. Let's examine the boundary conditions that can trip up even experienced developers."},"type":"text"},{"data":{"items":["**Single element array:** `[5]` — Both 'halves' are trivially sorted. Our check handles this correctly because low = mid = high.","**Two element array:** `[2, 1]` — mid = 0, so left 'half' is just [2]. Check: arr[0] ≤ arr[0]? Yes, so left is sorted. Correct!","**Two element array (not rotated):** `[1, 2]` — mid = 0, left half is [1]. Right half is [1, 2]. Check: arr[0] ≤ arr[0]? Yes. Both are valid.","**Minimum is at mid:** `[3, 4, 5, 1, 2]` — mid = 2 (value 5). arr[0]=3, arr[2]=5. Check: 3 ≤ 5? Yes. Left half [3,4,5] is sorted. Correct!","**Maximum is at mid:** `[5, 1, 2, 3, 4]` — mid = 2 (value 2). arr[0]=5, arr[2]=2. Check: 5 ≤ 2? No. Right half [2,3,4] is sorted. Correct!","**No rotation (fully sorted):** `[1, 2, 3, 4, 5]` — arr[0]=1, arr[2]=3. Check: 1 ≤ 3? Yes. Left half is sorted. (Right half is also sorted.)"],"title":{"icon":"AlertCircle","text":"Critical Edge Cases","type":"icon","color":"destructive","variant":"outline-circle"},"variant":"glass"},"type":"list"},{"data":{"fileName":"edge_cases_test.py","languages":[{"code":"$67","label":"Python","value":"python"}],"showLineNumbers":true},"type":"code"},{"data":{"icon":"AlertCircle","title":"Common Mistake: Off-by-One in Mid Calculation","content":"When computing mid, use `mid = low + (high - low) // 2` instead of `(low + high) // 2` to prevent integer overflow in languages like Java and C++. Python handles arbitrary precision integers, but the habit is worth developing.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":5},{"id":"strategic-value","title":"The Strategic Value of This Insight","content":[{"data":{"content":"Understanding that one half is always sorted isn't just a cute observation—it's the **key that unlocks binary search** in rotated arrays. Here's why:\n\n**Binary search requires a decision criterion.**\n\nIn standard binary search on a sorted array, the decision is simple:\n- If `target < arr[mid]`, search left\n- If `target > arr[mid]`, search right\n\nThis works because we *know* which direction contains smaller/larger values.\n\n**In a rotated array, we lost that guarantee... almost.**\n\nWe can't globally reason about which side has smaller or larger values. But we *can* reason about the **sorted half**:\n\n- If the sorted half is [4, 5, 6, 7], we know exactly what values are there\n- We can check: is our target in the range [4, 7]?\n- If yes, search that half. If no, search the other.\n\nThis transforms the problem from \"where should I look?\" to \"is my target in the portion I fully understand?\""},"type":"text"},{"data":{"left":[{"data":{"items":["Array is partially sorted, can't use binary search","Would need to find pivot first (extra O(log n))","Or resort to linear search O(n)","No clear decision at each step","Algorithm feels like guesswork"],"title":{"icon":"XCircle","text":"Without This Insight","type":"icon","color":"destructive","variant":"outline-circle"},"variant":"accent"},"type":"list"}],"right":[{"data":{"items":["At each step, one half is guaranteed sorted","Can make definitive decisions about sorted half","Single pass O(log n) is possible","Clear, systematic algorithm","Elegant extension of binary search"],"title":{"icon":"CheckCircle","text":"With This Insight","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}]},"type":"two-column"},{"data":{"icon":"Sparkles","title":"Preview of the Algorithm","content":"In the next page, we'll build the complete search algorithm. The structure will be: (1) Find mid, (2) Identify which half is sorted, (3) Check if target is in the sorted half's range, (4) Eliminate the other half. This single insight enables that entire strategy.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":6},{"id":"mental-model","title":"Building Your Mental Model","content":[{"data":{"content":"The best way to internalize this concept is to build a strong visual and intuitive mental model. Here are several ways to think about rotated arrays:"},"type":"text"},{"data":{"type":"ordered","items":["**The Mountain Range Model:** Imagine a sorted array as a mountain that rises from left to right. Rotation creates a 'cliff' where the mountain suddenly drops. When you look at any section, one side of the cliff is a smooth upward slope (sorted), and the other crosses the cliff (broken).","**The Clock Model:** Think of the array wrapped around a circular clock. The values increase as you go clockwise. Rotation just changes which position is '12 o'clock'. Any arc of less than 180° covers either the continuous increasing portion or crosses the 12 o'clock mark (the minimum).","**The Cut Deck Model:** A sorted array is a sorted deck of cards. Rotation is cutting the deck—taking the bottom portion and placing it on top. When you look at half the deck, either you see a continuous run from the original deck, or you see cards from both the top and bottom portions.","**The Two Runs Model:** A rotated array is simply two sorted runs concatenated: [large values in order] + [small values in order]. When you split at mid, one half contains only one run (sorted), and the other half might contain parts of both runs (broken)."],"title":"Mental Models for Rotated Arrays","variant":"accent"},"type":"list"},{"data":{"icon":"Lightbulb","title":"Whichever Model Clicks, Use It","content":"Different people find different models intuitive. The mountain model works for visual thinkers. The two-runs model works for those who think mathematically. Choose the one that helps you 'see' why one half must be sorted, and the algorithm will feel natural rather than memorized.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":7},{"id":"summary","title":"Summary: The Foundation for Rotated Array Search","content":[{"data":{"content":"We've established the fundamental insight that makes rotated array search possible. Let's consolidate what we've learned:"},"type":"text"},{"data":{"type":"ordered","items":["**A rotated sorted array has exactly two sorted runs** — the elements 'before' and 'after' the rotation point.","**When divided at mid, one half is always fully sorted** — because the rotation point can only be in one half.","**The check is simple: arr[low] ≤ arr[mid] means left is sorted** — otherwise, right is sorted.","**This single comparison takes O(1) time** — adding no overhead to binary search.","**This insight enables binary search in rotated arrays** — by giving us a portion we can reason about definitively.","**Edge cases are handled naturally** — single elements, two elements, and unrotated arrays all work correctly."],"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 you can identify which half is sorted, the next page shows how to build the complete search algorithm. We'll use this insight to make definitive decisions about which half to search—transforming the rotated array problem from daunting to elegant."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"You now understand the foundational insight for rotated array search: one half is always sorted, and a single O(1) check tells you which. This is the hardest part to truly internalize—the algorithm itself follows naturally from here. Next, we'll build the modified binary search strategy.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":8}],"isLocked":false},{"id":"seed_cd988168be773f2a1fc38d5cddaeaebc","title":"Modified Binary Search Strategy","order":1,"content":null,"isLocked":true},{"id":"seed_2f73391dbef432969a9795faed9c0853","title":"Handling Duplicates in Rotated Arrays","order":2,"content":null,"isLocked":true},{"id":"seed_062477c7726063301203bf1c06a8051f","title":"Time Complexity Analysis","order":3,"content":null,"isLocked":true}]}},"dataUpdateCount":1,"dataUpdatedAt":1792316336640,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["learningContent","getModule"],{"input":{"slug":"search-in-rotated-arrays"},"type":"query"}],"queryHash":"[[\"learningContent\",\"getModule\"],{\"input\":{\"slug\":\"search-in-rotated-arrays\"},\"type\":\"query\"}]"},{"dehydratedAt":1792316336657,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792316336655,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["learningContent","getProgress"],{"input":{"moduleId":"seed_0844cd36921eeb829425a91ddb53f42d"},"type":"query"}],"queryHash":"[[\"learningContent\",\"getProgress\"],{\"input\":{\"moduleId\":\"seed_0844cd36921eeb829425a91ddb53f42d\"},\"type\":\"query\"}]"},{"dehydratedAt":1792316336657,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792316336656,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["feedback","get"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_cd988168be773f2a1fc38d5cddaeaebc"},"type":"query"}],"queryHash":"[[\"feedback\",\"get\"],{\"input\":{\"contentId\":\"seed_cd988168be773f2a1fc38d5cddaeaebc\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792316336657,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792316336656,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["feedback","getUserLike"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_cd988168be773f2a1fc38d5cddaeaebc"},"type":"query"}],"queryHash":"[[\"feedback\",\"getUserLike\"],{\"input\":{\"contentId\":\"seed_cd988168be773f2a1fc38d5cddaeaebc\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792316336657,"state":{"data":{"json":[]},"dataUpdateCount":1,"dataUpdatedAt":1792316336656,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["highlights","getHighlights"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_cd988168be773f2a1fc38d5cddaeaebc"},"type":"query"}],"queryHash":"[[\"highlights\",\"getHighlights\"],{\"input\":{\"contentId\":\"seed_cd988168be773f2a1fc38d5cddaeaebc\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792316336657,"state":{"data":"$undefined","dataUpdateCount":0,"dataUpdatedAt":0,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"pending","fetchStatus":"fetching"},"queryKey":[["highlights","getPopularHighlights"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_cd988168be773f2a1fc38d5cddaeaebc","minCount":2},"type":"query"}],"queryHash":"[[\"highlights\",\"getPopularHighlights\"],{\"input\":{\"contentId\":\"seed_cd988168be773f2a1fc38d5cddaeaebc\",\"contentType\":\"LEARNING_PAGE\",\"minCount\":2},\"type\":\"query\"}]","promise":"$@68"}]},"children":"$L69"}]