Search in Rotated Sorted Array in DSA C++ - Build from Scratch

Search in Rotated Sorted Array

📖 Scenario: Imagine you have a list of numbers that was originally sorted from smallest to largest. But then, someone rotated it at some point, so the order is mixed. You want to find if a certain number is in this rotated list.

🎯 Goal: You will write a program to find the position of a given number in a rotated sorted array using an efficient search method.

📋 What You'll Learn

Create a vector called nums with the exact values: {4, 5, 6, 7, 0, 1, 2}

Create an integer variable called target and set it to 0

Write a function called search that takes nums and target and returns the index of target in nums or -1 if not found

Print the result of calling search(nums, target)

💡 Why This Matters

🌍 Real World

Rotated sorted arrays appear in systems where data is shifted or rotated, such as circular buffers or rotated logs. Efficient search helps quickly find needed information.

💼 Career

Understanding how to search in rotated sorted arrays is useful for software engineers working on performance-critical applications, embedded systems, or interview coding challenges.

1

Create the rotated sorted array

Create a vector called nums with the exact values {4, 5, 6, 7, 0, 1, 2}.

DSA C++

#include 
#include 

int main() {
    // Create vector nums with values {4, 5, 6, 7, 0, 1, 2}
    // Your code here
    return 0;
}

Hint

Use std::vector<int> nums = {4, 5, 6, 7, 0, 1, 2}; to create the vector.

2

Set the target number to search

Create an integer variable called target and set it to 0.

DSA C++

#include 
#include 

int main() {
    std::vector nums = {4, 5, 6, 7, 0, 1, 2};
    // Create int variable target and set it to 0
    // Your code here
    return 0;
}

Hint

Use int target = 0; to create the target variable.

3

Write the search function for rotated sorted array

Write a function called search that takes const std::vector<int>& nums and int target and returns the index of target in nums or -1 if not found. Use a binary search approach adapted for rotated arrays.

DSA C++

#include 
#include 

// Write search function here
// Your code here

int main() {
    std::vector nums = {4, 5, 6, 7, 0, 1, 2};
    int target = 0;

    return 0;
}

Hint

Use binary search with checks on which half is sorted to decide where to search next.

4

Print the search result

Print the result of calling search(nums, target).

DSA C++

#include 
#include 

int search(const std::vector& nums, int target) {
    int left = 0;
    int right = (int)nums.size() - 1;
    while (left  nums = {4, 5, 6, 7, 0, 1, 2};
    int target = 0;

    // Print the index of target in nums
    // Your code here
    return 0;
}

Hint

Use std::cout << search(nums, target) << std::endl; to print the result.