Find Minimum in Rotated Sorted Array in DSA Javascript

Mental Model

A rotated sorted array is like a sorted list that got shifted. The smallest number is where the shift happened.

Analogy: Imagine a clock face with numbers 1 to 12 in order. If you rotate the clock, the smallest number is where the new 'start' of the clock is.

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

Rotated array example:
[4] -> [5] -> [1] -> [2] -> [3] -> null
↑ (rotation point, minimum)

Dry Run Walkthrough

Input: array: [4, 5, 1, 2, 3]

Goal: Find the smallest number in the rotated sorted array efficiently

Step 1: Set left=0, right=4 (start and end indices)

Array: [4, 5, 1, 2, 3]
left=0 -> 4, right=4 -> 3

Why: We start searching between the whole array

Step 2: Calculate mid = Math.floor((0+4)/2) = 2, check value at mid=1

Array: [4, 5, 1, 2, 3]
left=0 -> 4, mid=2 -> 1, right=4 -> 3

Why: Mid helps us decide which half contains the minimum

Step 3: Compare mid value 1 with right value 3; since 1 < 3, move right to mid

Array: [4, 5, 1, 2, 3]
left=0 -> 4, right=2 -> 1

Why: Minimum must be at mid or to the left

Step 4: Calculate new mid = Math.floor((0+2)/2) = 1, mid value=5

Array: [4, 5, 1, 2, 3]
left=0 -> 4, mid=1 -> 5, right=2 -> 1

Why: Check middle of new search range

Step 5: Compare mid value 5 with right value 1; since 5 > 1, move left to mid+1

Array: [4, 5, 1, 2, 3]
left=2 -> 1, right=2 -> 1

Why: Minimum is to the right of mid

Step 6: Now left == right == 2, found minimum at index 2 with value 1

Array: [4, 5, 1, 2, 3]
Minimum = 1 at index 2

Why: Search narrowed to one element which is minimum

Result:

Minimum value is 1 at index 2

Annotated Code

DSA Javascript

class RotatedSortedArray {
  constructor(nums) {
    this.nums = nums;
  }

  findMin() {
    let left = 0;
    let right = this.nums.length - 1;

    while (left < right) {
      const mid = Math.floor((left + right) / 2);
      // If mid element is less than right element, min is at mid or left side
      if (this.nums[mid] < this.nums[right]) {
        right = mid; // move right to mid
      } else {
        left = mid + 1; // min is to the right of mid
      }
    }
    return this.nums[left]; // left == right is min index
  }
}

// Driver code
const arr = new RotatedSortedArray([4, 5, 1, 2, 3]);
console.log(arr.findMin());

while (left < right) {

loop until search space narrows to one element

const mid = Math.floor((left + right) / 2);

find middle index to split search space

if (this.nums[mid] < this.nums[right]) {

if mid value less than right, min is at mid or left side

right = mid;

move right pointer to mid to narrow search left

else { left = mid + 1; }

else min is right of mid, move left pointer

return this.nums[left];

return minimum value when left meets right

Output

1

Complexity Analysis

Time: O(log n) because we halve the search space each step using binary search

Space: O(1) because we use only a few variables, no extra space proportional to input

vs Alternative: Naive approach scans all elements O(n), this binary search method is faster for large arrays

Edge Cases

Array not rotated (e.g. [1, 2, 3, 4, 5])

Algorithm returns first element as minimum correctly

DSA Javascript

if (this.nums[mid] < this.nums[right]) { right = mid; }

Array with single element (e.g. [10])

Returns the single element as minimum

DSA Javascript

while (left < right) { ... } // loop skipped as left == right

Array rotated at last element (e.g. [2, 3, 4, 5, 1])

Correctly finds minimum at last index

DSA Javascript

else { left = mid + 1; }

When to Use This Pattern

When you see a sorted array that might be rotated and need the smallest element quickly, use binary search to find the rotation point efficiently.

Common Mistakes

Mistake: Comparing mid element with left instead of right pointer
Fix: Always compare mid with right element to decide search direction

Mistake: Using <= in while loop causing infinite loop
Fix: Use while (left < right) to ensure loop ends when pointers meet

Summary

Finds the smallest number in a rotated sorted array using binary search.

Use when you have a sorted array shifted and want to find the minimum quickly.

The minimum is the only element smaller than the element at the right pointer in the search range.

Practice

1. What is the main goal when finding the minimum in a rotated sorted array?

easy

A. To find the largest element in the array

B. To count the number of rotations

C. To find the smallest element after the rotation point

D. To sort the array again

Solution

1. Step 1: Understand the rotated sorted array

   A rotated sorted array is a sorted array shifted at some pivot. The smallest element is the rotation point.

2. Step 2: Identify the goal

   The goal is to find the smallest element, which is the minimum after rotation.

3. Final Answer:

   To find the smallest element after the rotation point -> Option C

4. Quick Check:

   Minimum element = smallest after rotation [OK]

Hint: Look for the smallest element where order breaks [OK]

Common Mistakes:

• Confusing minimum with maximum
• Trying to count rotations instead of finding minimum
• Assuming array is fully sorted without rotation

2. Which of the following is the correct syntax to start a binary search loop in JavaScript for finding minimum in rotated sorted array nums?

easy

A. while(left < right) { ... }

B. for(let left = 0, right = nums.length - 1; left <= right; )

C. for(let i = 0; i < nums.length; i++)

D. if(nums.length === 0) return -1

Solution

1. Step 1: Identify the loop type for binary search

   Binary search typically uses a while loop with condition left < right to narrow down the search space.

2. Step 2: Check options

   while(left < right) { ... } uses while(left < right), which is correct for binary search in this problem.

3. Final Answer:

   while(left < right) { ... } -> Option A

4. Quick Check:

   Binary search loop uses while(left < right) [OK]

Hint: Use while loop with left < right for binary search [OK]

Common Mistakes:

• Using for loop incorrectly for binary search
• Using <= instead of < causing infinite loops
• Not initializing left and right properly

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

function findMin(nums) {
  let left = 0, right = nums.length - 1;
  while (left < right) {
    let mid = Math.floor((left + right) / 2);
    if (nums[mid] > nums[right]) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  return nums[left];
}

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

medium

A. 1

B. 4

C. 7

D. 0

Solution

1. Step 1: Understand the binary search logic

   The code compares middle element with right element to decide which half contains the minimum.

2. Step 2: Trace the code with input [4,5,6,7,0,1,2]

   Initially left=0, right=6. Mid=3 (value 7). Since 7 > 2, left = mid+1 = 4. Now left=4, right=6. Mid=5 (value 1). 1 <= 2, so right=mid=5. Next left=4, right=5. Mid=4 (value 0). 0 <= 1, right=mid=4. Now left=4, right=4, loop ends. Return nums[4] = 0.

3. Final Answer:

   0 -> Option D

4. Quick Check:

   Minimum element found = 0 [OK]

Hint: Compare mid with right to decide search half [OK]

Common Mistakes:

• Returning nums[mid] instead of nums[left]
• Confusing comparison direction
• Not updating pointers correctly

4. Identify the bug in this code snippet for finding minimum in rotated sorted array:

function findMin(nums) {
  let left = 0, right = nums.length - 1;
  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (nums[mid] > nums[right]) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  return nums[left];
}

medium

A. The loop condition should be left < right, not left <= right

B. The mid calculation is incorrect

C. The return statement should be nums[right]

D. The comparison should be nums[mid] < nums[right]

Solution

1. Step 1: Analyze loop condition

   The loop uses left <= right, which can cause infinite loop or skip the correct minimum index.

2. Step 2: Correct loop condition

   Binary search for minimum in rotated array requires left < right to narrow search correctly without missing elements.

3. Final Answer:

   The loop condition should be left < right, not left <= right -> Option A

4. Quick Check:

   Use while(left < right) for correct binary search [OK]

Hint: Use strict less than in binary search loops [OK]

Common Mistakes:

• Using <= causing infinite loops
• Changing mid calculation unnecessarily
• Returning wrong index after loop

5. Given a rotated sorted array nums that may contain duplicates, which modification is needed in the binary search approach to correctly find the minimum?

hard

A. Return nums[mid] immediately when nums[mid] == nums[right]

B. When nums[mid] == nums[right], reduce right by 1 to skip duplicate

C. Always move left to mid + 1 when nums[mid] >= nums[right]

D. Sort the array first before applying binary search

Solution

1. Step 1: Understand duplicates effect

   Duplicates can cause ambiguity when nums[mid] equals nums[right], making it unclear which side to search.

2. Step 2: Modify binary search to handle duplicates

   When nums[mid] == nums[right], safely reduce right by 1 to skip duplicate and continue search.

3. Final Answer:

   When nums[mid] == nums[right], reduce right by 1 to skip duplicate -> Option B

4. Quick Check:

   Handle duplicates by shrinking right pointer [OK]

Hint: Skip duplicates by decrementing right when equal [OK]

Common Mistakes:

• Ignoring duplicates causing wrong minimum
• Moving left pointer incorrectly on equality
• Sorting array unnecessarily