Search in Rotated Sorted Array in DSA Typescript

Mental Model

We look for a number in a list that was sorted but then turned around at some point. We use a smart search that checks which part is still sorted to find the number quickly.

Analogy: Imagine a clock face with numbers in order, but someone rotated it so 12 is not at the top. To find a number, you check which half of the clock still has numbers in order and decide where to look next.

Original sorted array:
[1] -> [2] -> [3] -> [4] -> [5] -> [6] -> [7] -> null

Rotated array example:
[4] -> [5] -> [6] -> [7] -> [1] -> [2] -> [3] -> null
↑ start pointer
               ↑ mid pointer
                             ↑ end pointer

Dry Run Walkthrough

Input: array: [4,5,6,7,0,1,2], target: 0

Goal: Find the index of target 0 in the rotated sorted array

Step 1: Calculate mid index between start=0 and end=6; mid=3 (value=7)

[4] -> [5] -> [6] -> [7] -> [0] -> [1] -> [2]
start=0 (4), mid=3 (7), end=6 (2)

Why: We check middle to decide which half is sorted

Step 2: Check if left half [4..7] is sorted: yes, because 4 <= 7

[4] -> [5] -> [6] -> [7] -> [0] -> [1] -> [2]
left half sorted

Why: Knowing which half is sorted helps decide where target might be

Step 3: Check if target 0 is between start=4 and mid=7: no

[4] -> [5] -> [6] -> [7] -> [0] -> [1] -> [2]

Why: Target not in left sorted half, so search right half

Step 4: Move start to mid+1=4 to search right half

[4] -> [5] -> [6] -> [7] -> [0] -> [1] -> [2]
start=4 (0), end=6 (2)

Why: Focus search on right half where target may be

Step 5: Calculate mid between start=4 and end=6; mid=5 (value=1)

[4] -> [5] -> [6] -> [7] -> [0] -> [1] -> [2]
start=4 (0), mid=5 (1), end=6 (2)

Why: Check middle of new search range

Step 6: Check if left half [0..1] is sorted: yes, 0 <= 1

[4] -> [5] -> [6] -> [7] -> [0] -> [1] -> [2]

Why: Identify sorted half again

Step 7: Check if target 0 is between start=0 and mid=1: yes

[4] -> [5] -> [6] -> [7] -> [0] -> [1] -> [2]

Why: Target is in left sorted half, so search there

Step 8: Move end to mid-1=4 to narrow search

[4] -> [5] -> [6] -> [7] -> [0] -> [1] -> [2]
start=4 (0), end=4 (0)

Why: Narrow down to single element

Step 9: Calculate mid between start=4 and end=4; mid=4 (value=0)

[4] -> [5] -> [6] -> [7] -> [0] -> [1] -> [2]
start=4 (0), mid=4 (0), end=4 (0)

Why: Check the last element in range

Step 10: Found target at index 4

[4] -> [5] -> [6] -> [7] -> [0] -> [1] -> [2]
Target found at index 4

Why: Search complete

Result:

[4] -> [5] -> [6] -> [7] -> [0] -> [1] -> [2]
Target found at index 4

Annotated Code

DSA Typescript

class RotatedSortedArray {
  static search(nums: number[], target: number): number {
    let start = 0;
    let end = nums.length - 1;
    while (start <= end) {
      const mid = Math.floor((start + end) / 2);
      if (nums[mid] === target) {
        return mid; // found target
      }
      // Check if left half is sorted
      if (nums[start] <= nums[mid]) {
        // Target in left half?
        if (nums[start] <= target && target < nums[mid]) {
          end = mid - 1; // search left half
        } else {
          start = mid + 1; // search right half
        }
      } else {
        // Right half is sorted
        if (nums[mid] < target && target <= nums[end]) {
          start = mid + 1; // search right half
        } else {
          end = mid - 1; // search left half
        }
      }
    }
    return -1; // target not found
  }
}

// Driver code
const nums = [4,5,6,7,0,1,2];
const target = 0;
const index = RotatedSortedArray.search(nums, target);
if (index !== -1) {
  console.log(`Target found at index ${index}`);
} else {
  console.log("Target not found");
}

while (start <= end) {

loop to narrow search range until start passes end

const mid = Math.floor((start + end) / 2);

calculate middle index to check

if (nums[mid] === target) { return mid; }

check if mid element is target

if (nums[start] <= nums[mid]) {

check if left half is sorted

if (nums[start] <= target && target < nums[mid]) { end = mid - 1; } else { start = mid + 1; }

decide if target is in left half or right half

else { if (nums[mid] < target && target <= nums[end]) { start = mid + 1; } else { end = mid - 1; } }

right half sorted case, decide where target lies

Output

Target found at index 4

Complexity Analysis

Time: O(log n) because each step halves the search range

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Compared to linear search O(n), this binary search approach is much faster on large arrays

Edge Cases

empty array

returns -1 immediately since start > end

DSA Typescript

while (start <= end) {

array with one element equal to target

returns index 0 immediately

DSA Typescript

if (nums[mid] === target) { return mid; }

array with one element not equal to target

returns -1 after one check

DSA Typescript

while (start <= end) {

target not in array

returns -1 after search exhausts

DSA Typescript

return -1;

When to Use This Pattern

When you see a sorted array that has been rotated and need to find an element quickly, use this pattern of checking sorted halves to apply binary search efficiently.

Common Mistakes

Mistake: Not checking which half is sorted before deciding where to search
Fix: Always check if left half or right half is sorted before moving pointers

Mistake: Using <= or < incorrectly causing infinite loops or wrong results
Fix: Use consistent comparison operators to correctly include or exclude mid element

Summary

Finds a target value in a rotated sorted array using modified binary search.

Use when searching in arrays that were sorted but then rotated at some pivot.

The key is to identify which half is sorted to decide where to continue searching.