Find Minimum in Rotated Sorted Array in DSA Java

Mental Model

A rotated sorted array is like a sorted list that has been shifted. The smallest element is the point where the shift happened.

Analogy: Imagine a clock face with numbers 1 to 12 in order. If you rotate the clock so that 3 is at the top, the smallest number is where the rotation starts, like the new '12'.

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

Rotated array example:
[4] -> [5] -> [1] -> [2] -> [3] -> null
          ↑
       smallest element here

Dry Run Walkthrough

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

Goal: Find the minimum element in the rotated sorted array efficiently

Step 1: Set low=0, high=4 (start and end indices)

array: [4, 5, 1, 2, 3], low=0, high=4

Why: We start searching between the whole array

Step 2: Calculate mid = (0+4)/2 = 2, check array[mid]=1

array: [4, 5, 1, 2, 3], low=0, mid=2, high=4

Why: Mid helps us decide which half contains the minimum

Step 3: Compare array[mid]=1 with array[high]=3; since 1 < 3, set high=mid=2

array: [4, 5, 1, 2, 3], low=0, high=2

Why: Minimum must be in left half including mid

Step 4: Calculate mid = (0+2)/2 = 1, check array[mid]=5

array: [4, 5, 1, 2, 3], low=0, mid=1, high=2

Why: Narrow down search to find minimum

Step 5: Compare array[mid]=5 with array[high]=1; since 5 > 1, set low=mid+1=2

array: [4, 5, 1, 2, 3], low=2, high=2

Why: Minimum must be in right half excluding mid

Step 6: Now low=high=2, minimum found at index 2 with value 1

array: [4, 5, 1, 2, 3], low=2, high=2 -> minimum=1

Why: Search narrowed to one element which is minimum

Result:

array: [4, 5, 1, 2, 3], minimum element = 1 at index 2

Annotated Code

DSA Java

public class RotatedArrayMin {
    public static int findMin(int[] nums) {
        int low = 0;
        int high = nums.length - 1;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] > nums[high]) {
                low = mid + 1; // minimum in right half
            } else {
                high = mid; // minimum in left half including mid
            }
        }
        return nums[low];
    }

    public static void main(String[] args) {
        int[] nums = {4, 5, 1, 2, 3};
        int min = findMin(nums);
        System.out.println("Minimum element: " + min);
    }
}

while (low < high) {

loop until search space narrows to one element

int mid = low + (high - low) / 2;

calculate middle index to split search space

if (nums[mid] > nums[high]) {

if mid element greater than high, minimum is in right half

low = mid + 1; // minimum in right half

move low pointer to mid+1 to discard left half

} else {

otherwise minimum is in left half including mid

high = mid; // minimum in left half including mid

move high pointer to mid to keep left half

return nums[low];

return the minimum element found at low

Output

Minimum element: 1

Complexity Analysis

Time: O(log n) because the search space is halved each step using binary search

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

vs Alternative: Compared to scanning all elements O(n), this binary search approach is much faster for large arrays

Edge Cases

array not rotated (fully sorted)

minimum is the first element, found quickly

DSA Java

while (low < high) {

array rotated by one element

algorithm still finds minimum correctly by narrowing search

DSA Java

if (nums[mid] > nums[high]) {

array with two elements rotated

minimum found by comparing mid and high elements

DSA Java

else { high = mid; }

When to Use This Pattern

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

Common Mistakes

Mistake: Using linear search instead of binary search, causing slow performance
Fix: Use binary search logic comparing mid and high elements to halve search space

Mistake: Incorrectly updating low or high pointers causing infinite loops
Fix: Ensure low moves to mid+1 when nums[mid] > nums[high], else high moves to mid

Summary

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

Use when you have a sorted array shifted at some pivot and want the minimum quickly.

The key insight is comparing middle and end elements to decide which half contains the minimum.

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 find the smallest element after the rotation point

C. To count the number of rotations

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 minimum element

   The minimum element is the smallest value after the rotation, which is the point where the order breaks.

3. Final Answer:

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

4. Quick Check:

   Minimum element = smallest after rotation [OK]

Hint: Look for the point where order breaks to find minimum [OK]

Common Mistakes:

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

2. Which Java syntax correctly declares a method to find the minimum in a rotated sorted array?

easy

A. public int findMin(int[] nums) {}

B. int findMin(int nums) {}

C. void findMin(int[] nums) {}

D. public static findMin(int[] nums) {}

Solution

1. Step 1: Check method return type and parameters

   The method should return an int (the minimum value) and accept an int array parameter.

2. Step 2: Validate Java method syntax

   public int findMin(int[] nums) {} uses 'public int findMin(int[] nums) {}' which is correct Java syntax for this method.

3. Final Answer:

   public int findMin(int[] nums) {} -> Option A

4. Quick Check:

   Correct method signature = public int findMin(int[] nums) {} [OK]

Hint: Method must return int and accept int array parameter [OK]

Common Mistakes:

• Missing return type or using void incorrectly
• Incorrect parameter syntax
• Missing access modifier or static keyword incorrectly

3. What is the output of the following code snippet?

int[] nums = {4,5,6,7,0,1,2};
System.out.println(findMin(nums));

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

medium

A. 2

B. 4

C. 7

D. 0

Solution

1. Step 1: Understand the binary search logic

   The code uses binary search to find the minimum by comparing middle and right elements, narrowing the search space.

2. Step 2: Trace the loop with given array

   Array: [4,5,6,7,0,1,2] - mid=3 (value 7), 7 > 2, so left = mid+1 = 4 - left=4, right=6 - mid=5 (value 1), 1 <= 2, so right = mid = 5 - left=4, right=5 - mid=4 (value 0), 0 <= 1, so right = mid = 4 Loop ends when left == right == 4, nums[4] = 0.

3. Final Answer:

   0 -> Option D

4. Quick Check:

   Minimum element found = 0 [OK]

Hint: Compare mid and right to narrow search for minimum [OK]

Common Mistakes:

• Returning nums[mid] instead of nums[left]
• Confusing comparison direction in binary search
• Not updating left or right correctly

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

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

medium

A. The return statement should be 'nums[right]'

B. The mid calculation is incorrect

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

D. The array should be sorted before searching

Solution

1. Step 1: Analyze the loop condition

   The loop uses 'left <= right', which can cause infinite loop or index errors because left can go beyond right.

2. Step 2: Correct the loop condition

   Changing the condition to 'left < right' ensures the loop stops when left meets right, correctly identifying the minimum index.

3. Final Answer:

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

4. Quick Check:

   Loop condition must be 'left < right' [OK]

Hint: Use 'left < right' to avoid infinite loops in binary search [OK]

Common Mistakes:

• Using 'left <= right' causing infinite loops
• Incorrectly adjusting right pointer
• Returning wrong array element after loop

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

int[] nums = {2,2,2,0,1,2};

hard

A. Add a condition to reduce right by one when nums[mid] equals nums[right]

B. Ignore duplicates and proceed as usual

C. Sort the array before searching

D. Use linear search instead of binary search

Solution

1. Step 1: Understand the effect of duplicates

   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], reduce right by one to shrink search space safely without missing minimum.

3. Final Answer:

   Add a condition to reduce right by one when nums[mid] equals nums[right] -> Option A

4. Quick Check:

   Handle duplicates by shrinking right pointer [OK]

Hint: When equal, reduce right pointer to handle duplicates [OK]

Common Mistakes:

• Ignoring duplicates causing wrong minimum
• Sorting array which is inefficient
• Switching to linear search unnecessarily