Search in Rotated Sorted Array - JS Solution

Editorial

Editorial solutions and visualizations are prepared with care, but we do not guarantee 100% accuracy or completeness. Please use your own judgment to verify results. Visucodize is not responsible for decisions made based on this content.

const LEFT = 'left', LEFT_COLOR = 'orange';
const RIGHT = 'right', RIGHT_COLOR = 'blue';
const MIDDLE = 'middle', MID_COLOR = 'gray';
const MATCH_COLOR = 'green';

function visMainFunction(inputNums, target) {
    initClassProperties();

    startBatch();
    const nums = VisArray.from(inputNums);
    let left = 0;
    let right = nums.length - 1;

    makeVisVariable(target).options({label: 'target'}).createVis(true);
    makeVisVariable(left).registerAsIndexPointer(nums, LEFT);
    makeVisVariable(right).registerAsIndexPointer(nums, RIGHT);
    endBatch();

    explanationAndColorPaletteNotificaitons()

    notification(`
        🔍 We’re searching a <b>rotated sorted array</b> using binary search.<br/>
        We keep three pointers:<br/>
        • <b>${makeColoredSpan('left', LEFT_COLOR)}</b> → the start index of the current search range.<br/>
        • <b>${makeColoredSpan('right', RIGHT_COLOR)}</b> → the end index of the current search range.<br/>
        • <b>${makeColoredSpan('mid', MID_COLOR)}</b> → the middle index between <b>${makeColoredSpan('left', LEFT_COLOR)}</b> and <b>${makeColoredSpan('right', RIGHT_COLOR)}</b>.<br/><br/>
        At each step, we first check:<br/>
        • If <code>nums[${makeColoredSpan('mid', MID_COLOR)}] === target</code>, we have found the answer and return <b>${makeColoredSpan('mid', MID_COLOR)}</b> immediately.<br/><br/>
        Otherwise, we compare <code>nums[${makeColoredSpan('mid', MID_COLOR)}]</code> with <code>nums[${makeColoredSpan('right', RIGHT_COLOR)}]</code> to determine which segment <b>${makeColoredSpan('mid', MID_COLOR)}</b> lies in:<br/>
        • If <code>nums[${makeColoredSpan('mid', MID_COLOR)}] ≤ nums[${makeColoredSpan('right', RIGHT_COLOR)}]</code>, then <b>${makeColoredSpan('mid', MID_COLOR)} is in the second sorted segment</b>, because every value in the first sorted segment is greater than <code>nums[${makeColoredSpan('right', RIGHT_COLOR)}]</code>. Therefore, the <b>right half ([${makeColoredSpan('mid', MID_COLOR)}..${makeColoredSpan('right', RIGHT_COLOR)}])</b> is <b>assured to be sorted</b>.<br/>
        • Otherwise (if <code>nums[${makeColoredSpan('mid', MID_COLOR)}] > nums[${makeColoredSpan('right', RIGHT_COLOR)}]</code>), <b>${makeColoredSpan('mid', MID_COLOR)} is in the first sorted segment</b>, because no value in the second sorted segment can exceed <code>nums[${makeColoredSpan('right', RIGHT_COLOR)}]</code>. Therefore, the <b>left half ([${makeColoredSpan('left', LEFT_COLOR)}..${makeColoredSpan('mid', MID_COLOR)}])</b> is <b>assured to be sorted</b>.<br/><br/>
        Then we range-check the <b>half assured to be sorted</b>: if the target lies within its bounds, continue there; otherwise, search the other half.
    `);

    while (left <= right) {
        startPartialBatch();

        const mid = Math.floor((left + right) / 2);
        const midVal = nums[mid];
        const rightVal = nums[right];
        const leftVal = nums[left];

        const midVisManager = nums.makeVisManagerForIndex(mid);
        midVisManager.addClass(MIDDLE);

        notification(`
            📌 Checking <b>${makeColoredSpan('mid', MID_COLOR)}</b> ${makeColoredSpan(mid, MID_COLOR)}:
            <code>nums[${makeColoredSpan('mid', MID_COLOR)}]</code> = <b>${makeColoredSpan(midVal, MID_COLOR)}</b>.
        `);

        if (target === midVal) {
            midVisManager.setProp('backgroundColor', MATCH_COLOR);
            notification(`✅ Found target <b>${makeColoredSpan(target, MATCH_COLOR)}</b> at index <b>${makeColoredSpan(mid, MID_COLOR)}</b>.`);
            return mid;
        }

        if (midVal <= rightVal) {  // Right half ([mid..right]) is assured-sorted
            notification(`
                🧭 Since <code>nums[${makeColoredSpan('mid', MID_COLOR)}]</code> (${makeColoredSpan(midVal, MID_COLOR)}) ≤
                <code>nums[${makeColoredSpan('right', RIGHT_COLOR)}]</code> (${makeColoredSpan(rightVal, RIGHT_COLOR)}),
                <b>${makeColoredSpan('mid', MID_COLOR)} is in the second sorted segment</b> (all first-segment values are &gt; <code>nums[${makeColoredSpan('right', RIGHT_COLOR)}]</code>).<br/>
                Therefore, the <b>right half ([${makeColoredSpan('mid', MID_COLOR)}..${makeColoredSpan('right', RIGHT_COLOR)}])</b> is <b>assured to be sorted</b>.
            `);

            if (target > midVal && target <= rightVal) {
                notification(`
                    🎯 The target <b>${makeColoredSpan(target, MATCH_COLOR)}</b> lies within the <b>assured-sorted</b>
                    <b>right half ([${makeColoredSpan('mid', MID_COLOR)}..${makeColoredSpan('right', RIGHT_COLOR)}])</b>, i.e.,
                    <b>(${makeColoredSpan(midVal, MID_COLOR)}, ${makeColoredSpan(rightVal, RIGHT_COLOR)}]</b>.<br/>
                    ➡️ Continue in this half: set <b>${makeColoredSpan('left', LEFT_COLOR)} = ${makeColoredSpan('mid', MID_COLOR)} + 1</b>.
                `);
                left = mid + 1;
            } else {
                notification(`
                    🚫 The target <b>${makeColoredSpan(target, MATCH_COLOR)}</b> is <b>outside</b> the <b>assured-sorted</b>
                    <b>right half ([${makeColoredSpan('mid', MID_COLOR)}..${makeColoredSpan('right', RIGHT_COLOR)}])</b>, i.e.,
                    <b>(${makeColoredSpan(midVal, MID_COLOR)}, ${makeColoredSpan(rightVal, RIGHT_COLOR)}]</b>.<br/>
                    ⬅️ Search the <b>other half</b>: set <b>${makeColoredSpan('right', RIGHT_COLOR)} = ${makeColoredSpan('mid', MID_COLOR)} - 1</b>.
                `);
                right = mid - 1;
            }
        } else {  // Left half ([left..mid]) is assured-sorted
            notification(`
                🧭 Since <code>nums[${makeColoredSpan('mid', MID_COLOR)}]</code> (${makeColoredSpan(midVal, MID_COLOR)}) &gt; 
                <code>nums[${makeColoredSpan('right', RIGHT_COLOR)}]</code> (${makeColoredSpan(rightVal, RIGHT_COLOR)}), 
                <b>${makeColoredSpan('mid', MID_COLOR)} is in the first sorted segment</b> (no value in the second sorted segment can be greater than <code>nums[${makeColoredSpan('right', RIGHT_COLOR)}]</code>).<br/>
                Therefore, the <b>left half ([${makeColoredSpan('left', LEFT_COLOR)}..${makeColoredSpan('mid', MID_COLOR)}])</b> is <b>assured to be sorted</b>.
            `);

            if (target >= leftVal && target < midVal) {
                notification(`
                    🎯 The target <b>${makeColoredSpan(target, MATCH_COLOR)}</b> lies within the <b>assured-sorted</b>
                    <b>left half ([${makeColoredSpan('left', LEFT_COLOR)}..${makeColoredSpan('mid', MID_COLOR)}])</b>, i.e.,
                    <b>[${makeColoredSpan(leftVal, LEFT_COLOR)}, ${makeColoredSpan(midVal, MID_COLOR)})</b>.<br/>
                    ⬅️ Continue in this half: set <b>${makeColoredSpan('right', RIGHT_COLOR)} = ${makeColoredSpan('mid', MID_COLOR)} - 1</b>.
                `);
                right = mid - 1;
            } else {
                notification(`
                    🚫 The target <b>${makeColoredSpan(target, MATCH_COLOR)}</b> is <b>outside</b> the <b>assured-sorted</b>
                    <b>left half ([${makeColoredSpan('left', LEFT_COLOR)}..${makeColoredSpan('mid', MID_COLOR)}])</b>, i.e.,
                    <b>[${makeColoredSpan(leftVal, LEFT_COLOR)}, ${makeColoredSpan(midVal, MID_COLOR)})</b>.<br/>
                    ➡️ Search the <b>other half</b>: set <b>${makeColoredSpan('left', LEFT_COLOR)} = ${makeColoredSpan('mid', MID_COLOR)} + 1</b>.
                `);
                left = mid + 1;
            }
        }

        midVisManager.removeClass(MIDDLE);
        endBatch();
    }

    notification(`❌ Target <b>${makeColoredSpan(target, MATCH_COLOR)}</b> is <b>not found</b> in <code>nums</code>.`);
    return -1;
}

function explanationAndColorPaletteNotificaitons() {
    explanationNotification();

    // Then show the color palette legend
    notification(`
      🎨 <b>Color Palette & Pointer Legend</b><br/>
      • ${makeColoredSpan('left', LEFT_COLOR)} — <i>left pointer</i> color for both <b>left index</b> and <b>left value</b>.<br/>
      • ${makeColoredSpan('right', RIGHT_COLOR)} — <i>right pointer</i> color for both <b>right index</b> and <b>right value</b>.<br/>
      • ${makeColoredSpan('mid', MID_COLOR)} — <i>mid pointer</i> color for both <b>mid index</b> and <b>mid value</b>.<br/>
      • ${makeColoredSpan('target / match', MATCH_COLOR)} — highlight color when a value matches the target.<br/>
    `);
}

function initClassProperties() {
    setClassProperties(RIGHT, { backgroundColor: RIGHT_COLOR });
    setClassProperties(LEFT,  { backgroundColor: LEFT_COLOR  });
    setClassProperties(MIDDLE,{ backgroundColor: MID_COLOR   });
}

Approach

Problem

Given a rotated sorted array of distinct integers and a target, return the index of the target or -1 if not found, in O(log n) time.

Pointers

left — start index of the current search range
right — end index of the current search range
mid — middle index: Math.floor((left + right) / 2)

Segments in a Rotated Array

A rotation of a strictly increasing array splits it into two sorted segments:

First sorted segment — the left portion (before the rotation point) whose values are all greater than every value in the second segment. This segment can be empty if the array is not rotated (fully increasing).
Second sorted segment — the right portion (from the rotation point to the end) that is strictly increasing. This segment can be the entire array if there is no rotation.

Key Idea

During each binary-search step we follow three checks:

✅ First, if nums[mid] === target, we immediately return mid.
Otherwise, compare nums[mid] with nums[right] to decide which sorted segment mid belongs to, and therefore which half is assured to be sorted.

How we classify `mid`

If nums[mid] ≤ nums[right], then mid is in the second sorted segment, because every value in the first sorted segment is greater than nums[right].
Therefore, the right half ([mid..right]) is assured to be sorted.
Otherwise (if nums[mid] > nums[right]), mid is in the first sorted segment, because no value in the second sorted segment can exceed nums[right].
Therefore, the left half ([left..mid]) is assured to be sorted.

Range Check on the Half Assured to Be Sorted

After identifying the assured-sorted half, we check whether the target lies within its bounds:

If the right half is assured-sorted (nums[mid] ≤ nums[right]):
If the target lies within bounds (nums[mid], nums[right]], continue on the right: left = mid + 1.
Otherwise, search the other half: right = mid - 1.
If the left half is assured-sorted (nums[mid] > nums[right]):
If the target lies within bounds [nums[left], nums[mid]), continue on the left: right = mid - 1.
Otherwise, search the other half: left = mid + 1.

Why This Works

nums[right] serves as a boundary: all values in the second segment are ≤ nums[right], all values in the first segment are > nums[right].
Comparing nums[mid] with nums[right] reveals which segment mid belongs to, so one half is assured to be sorted.
Once a half is assured sorted, a simple range check decides whether to continue in that half or switch to the other, maintaining O(log n) complexity.

Time Complexity

O(log n)
Each step of binary search discards half of the remaining range by updating either left or right. The number of iterations is therefore logarithmic in the array length n.

Space Complexity

O(1)
Only a constant number of variables (left, right, mid) are used, regardless of input size.

Input-1

Search in Rotated Sorted Array - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

Approach

Problem

Pointers

Segments in a Rotated Array

Key Idea

How we classify mid

Range Check on the Half Assured to Be Sorted

Why This Works

Time Complexity

Space Complexity

How we classify `mid`