Find Minimum in Rotated Sorted Array in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Find minimum element output after rotation

What is the output of the following C++ code that finds the minimum element in a rotated sorted array?

DSA C++

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

int main() {
    vector<int> nums = {4,5,6,7,0,1,2};
    cout << findMin(nums) << endl;
    return 0;
}

A 2

B 1

C 0

D 4

💡 Hint

Think about where the smallest element lies in a rotated sorted array.

The code uses binary search to find the minimum element. Since the array is rotated, the minimum is the only element smaller than the last element in the array segment. The code narrows down to index 4 where the value is 0.

❓ Predict Output

intermediate

Minimum element in a rotated array with duplicates

What will be the output of this code when the input array contains duplicates?

DSA C++

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

int main() {
    vector<int> nums = {2,2,2,0,1,2};
    cout << findMin(nums) << endl;
    return 0;
}

A 2

B 0

C 1

D Error

💡 Hint

Duplicates require a slight modification in the binary search approach.

When duplicates exist, if nums[mid] equals nums[right], we reduce right by one to skip duplicates. The minimum element here is 0 at index 3.

🔧 Debug

advanced

Identify the error in this minimum finder code

What error will this code produce when trying to find the minimum in a rotated sorted array?

DSA C++

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

int main() {
    vector<int> nums = {3,4,5,1,2};
    cout << findMin(nums) << endl;
    return 0;
}

A Runtime error: out_of_range

B Output: 1

C Output: 3

D Infinite loop

💡 Hint

Check the loop condition and how left and right pointers move.

The loop condition allows left to go beyond right, and right is set to mid - 1 which can cause left to exceed array bounds. Accessing nums[left] after loop can cause out_of_range error.

❓ Predict Output

advanced

Output of minimum finder on a non-rotated sorted array

What is the output of this code when the input array is sorted but not rotated?

DSA C++

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

int main() {
    vector<int> nums = {1,2,3,4,5};
    cout << findMin(nums) << endl;
    return 0;
}

A 1

B 5

C 3

D 0

💡 Hint

If the array is not rotated, the minimum is the first element.

The code correctly returns the first element 1 as the minimum in a sorted array without rotation.

🧠 Conceptual

expert

Why binary search works for finding minimum in rotated sorted array

Which statement best explains why binary search can be used to find the minimum element in a rotated sorted array?

A Because the array elements are unique and binary search only works on unique elements.

B Because the array is rotated, the minimum element is always the last element.

C Because the minimum element is always at the middle index after rotation.

D Because the array is sorted, and rotation preserves sorted order in two parts, allowing binary search to discard half the array each step.

💡 Hint

Think about how rotation affects sorted order and how binary search uses order.

The rotated array consists of two sorted subarrays. Binary search compares middle and right elements to decide which half contains the minimum, discarding the other half each step.