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.

Practice

1. What is the main challenge when searching in a rotated sorted array compared to a normal sorted array?

easy

A. The array is split into two sorted parts, making direct binary search tricky

B. The array elements are all the same

C. The array is sorted in descending order

D. The array contains negative numbers

Solution

1. Step 1: Understand the array structure

   A rotated sorted array is originally sorted but then rotated at some pivot, splitting it into two sorted parts.

2. Step 2: Identify the challenge for binary search

   Because of the rotation, a simple binary search can't be applied directly since the array is not fully sorted in one direction.

3. Final Answer:

   The array is split into two sorted parts, making direct binary search tricky -> Option A

4. Quick Check:

   Rotation splits array = search challenge [OK]

Hint: Look for the pivot splitting sorted parts [OK]

Common Mistakes:

• Assuming array is fully sorted
• Ignoring the rotation pivot
• Thinking all elements are equal

2. Which of the following TypeScript function signatures correctly represents a search function for a rotated sorted array?

easy

A. function search(nums: number[], target: number): number

B. function search(nums: string[], target: string): boolean

C. function search(nums: number): number

D. function search(target: number, nums: number[]): number

Solution

1. Step 1: Check parameter types and order

   The function should accept an array of numbers and a target number to find, returning the index (number).

2. Step 2: Validate signature correctness

   function search(nums: number[], target: number): number matches this: array first, target second, returns number index.

3. Final Answer:

   function search(nums: number[], target: number): number -> Option A

4. Quick Check:

   Correct params and return type = function search(nums: number[], target: number): number [OK]

Hint: Array first, target second, return index number [OK]

Common Mistakes:

• Swapping parameter order
• Wrong parameter types
• Wrong return type

3. What will be the output of the following TypeScript code?

function search(nums: number[], target: number): number {
  let left = 0, right = nums.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) return mid;
    if (nums[left] <= nums[mid]) {
      if (nums[left] <= target && target < nums[mid]) right = mid - 1;
      else left = mid + 1;
    } else {
      if (nums[mid] < target && target <= nums[right]) left = mid + 1;
      else right = mid - 1;
    }
  }
  return -1;
}

console.log(search([4,5,6,7,0,1,2], 0));

medium

A. -1

B. 0

C. 4

D. 6

Solution

1. Step 1: Trace the binary search on rotated array

   Array: [4,5,6,7,0,1,2], target: 0. Mid index starts at 3 (value 7). Left half is sorted (4 to 7). Target 0 is not in left half, so search right half.

2. Step 2: Narrow down to target index

   Right half is [0,1,2], mid recalculated to index 5 (value 1). Target 0 is less than 1, so search left half of right side. Finally, target found at index 4.

3. Final Answer:

   4 -> Option C

4. Quick Check:

   Target 0 found at index 4 [OK]

Hint: Check sorted half, decide search side [OK]

Common Mistakes:

• Not updating left/right correctly
• Confusing mid calculation
• Assuming full array sorted

4. Identify the bug in this TypeScript function for searching in a rotated sorted array:

function search(nums: number[], target: number): number {
  let left = 0, right = nums.length - 1;
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) return mid;
    if (nums[left] <= nums[mid]) {
      if (nums[left] <= target && target < nums[mid]) right = mid - 1;
      else left = mid + 1;
    } else {
      if (nums[mid] < target && target <= nums[right]) left = mid + 1;
      else right = mid - 1;
    }
  }
  return -1;
}

medium

A. The function should return 'left' instead of '-1' when not found

B. The loop condition should be 'left <= right' instead of 'left < right'

C. The target comparison should use '>' instead of '<'

D. The mid calculation is incorrect

Solution

1. Step 1: Analyze loop condition impact

   The loop uses 'left < right', which can miss checking when left equals right, possibly skipping the last element.

2. Step 2: Correct loop condition for full search

   Changing to 'left <= right' ensures all elements are checked, including when left equals right.

3. Final Answer:

   The loop condition should be 'left <= right' instead of 'left < right' -> Option B

4. Quick Check:

   Loop must include equality to check all elements [OK]

Hint: Use <= to include last element in search [OK]

Common Mistakes:

• Using < instead of <= in loop
• Miscalculating mid index
• Wrong target comparison operators

5. Given a rotated sorted array [15, 18, 2, 3, 6, 12], which sequence of mid indices will the binary search check when searching for target 3 using the standard rotated array search algorithm?

hard

A. [0, 2, 3]

B. [2, 1, 3]

C. [3, 2, 4]

D. [2, 4, 3]

Solution

1. Step 1: Calculate initial mid and check halves

   Array: [15,18,2,3,6,12], left=0, right=5, mid = (0+5)//2=2 (value 2). Target 3 > 2, right half is checked next.

2. Step 2: Update pointers and find next mid

   Left=3, right=5, mid = (3+5)//2=4 (value 6). Target 3 < 6, so search left half: right=3.

3. Step 3: Final mid calculation

   Left=3, right=3, mid=3 (value 3), target found.

4. Final Answer:

   [2, 4, 3] -> Option D

5. Quick Check:

   Mid indices checked: 2, 4, 3 [OK]

Hint: Track left, right, mid updates carefully [OK]

Common Mistakes:

• Wrong mid calculation
• Not updating left/right correctly
• Assuming linear search order