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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of search in rotated sorted array

What is the output of the following C++ code that searches for a target in a rotated sorted array?

DSA C++

int search(const vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 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;
}

int main() {
    vector<int> arr = {4,5,6,7,0,1,2};
    int target = 0;
    cout << search(arr, target);
    return 0;
}

A -1

B 0

C 4

D 6

💡 Hint

Think about where the target 0 is located in the rotated array and how the binary search narrows down the search space.

The target 0 is at index 4 in the rotated sorted array. The binary search correctly finds it and returns 4.

❓ Predict Output

intermediate

Output of search for missing element

What is the output of the following code when searching for a target not present in the rotated sorted array?

DSA C++

int search(const vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 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;
}

int main() {
    vector<int> arr = {4,5,6,7,0,1,2};
    int target = 3;
    cout << search(arr, target);
    return 0;
}

A 6

B -1

C 0

D 3

💡 Hint

If the target is not found, the function returns -1.

The target 3 is not in the array, so the function returns -1.

🧠 Conceptual

advanced

Why binary search works on rotated sorted arrays

Why can binary search be applied to a rotated sorted array to find a target efficiently?

A Because at least one half of the array is always sorted, allowing us to decide which half to search next.

B Because the array is fully sorted, so normal binary search applies without changes.

C Because the array elements are all unique, so we can use hashing instead.

D Because the array is rotated, we must search both halves every time.

💡 Hint

Think about how the array is split and what property remains after rotation.

In a rotated sorted array, one half is always sorted. This property lets us decide which half to discard and which to keep searching, enabling efficient binary search.

🔧 Debug

advanced

Identify the bug in rotated array search code

What error will the following code produce when searching in a rotated sorted array?

DSA C++

int search(const vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int mid = left + (right - left) / 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;
}

A Infinite loop because 'left' and 'right' never change.

B Syntax error due to missing semicolon.

C Returns wrong index because mid calculation is incorrect.

D May miss the target if it is at index 'right' due to loop condition 'left < right'.

💡 Hint

Check the loop condition and what happens when left equals right.

The loop condition 'left < right' excludes the case when left == right, so if the target is at index right, it may be missed. The correct condition should be 'left <= right'.

🚀 Application

expert

Find minimum element index in rotated sorted array

Given a rotated sorted array with unique elements, which code snippet correctly finds the index of the minimum element?

A

int findMinIndex(const 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 left;
}

B

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

C

int findMinIndex(const vector<int>& nums) {
    int minIndex = 0;
    for (int i = 1; i < nums.size(); i++) {
        if (nums[i] < nums[minIndex]) minIndex = i;
    }
    return minIndex;
}

D

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

💡 Hint

The minimum element is the only element where the previous element is greater, or it is the smallest in the rotated array.

Option A correctly uses binary search to find the minimum by comparing mid with right. If nums[mid] > nums[right], the minimum is in the right half; else in the left half including mid.