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 the list at some unknown point, so the order is mixed but still partially sorted. You want to find if a certain number is in this rotated list.

🎯 Goal: You will write a program to search for a target number in a rotated sorted array using a smart method that works faster than checking every number one by one.

📋 What You'll Learn

Create an integer array 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 method called Search that takes nums and target as inputs 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 searching 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 coding interviews.

1

Create the rotated sorted array

Create an integer array called nums with these exact values: 4, 5, 6, 7, 0, 1, 2

DSA C#

// Create the rotated sorted array
// Your code here

Hint

Use int[] nums = {4, 5, 6, 7, 0, 1, 2}; to create the array.

2

Set the target number to search

Create an integer variable called target and set it to 0

DSA C#

int[] nums = {4, 5, 6, 7, 0, 1, 2};
// Create the target variable
// Your code here

Hint

Use int target = 0; to set the target number.

3

Write the Search method to find the target index

Write a method called Search that takes int[] nums and int target as inputs and returns the index of target in nums or -1 if not found. Use a while loop with variables left and right to perform a binary search adapted for rotated arrays.

DSA C#

int[] nums = {4, 5, 6, 7, 0, 1, 2};
int target = 0;

// Write the Search method below
// Your code here

Hint

Use a binary search approach with left, right, and mid indexes. Check which side is sorted and decide where to move.

4

Print the index of the target

Print the result of calling Search(nums, target)

DSA C#

int[] nums = {4, 5, 6, 7, 0, 1, 2};
int target = 0;

int Search(int[] nums, int target)
{
    int left = 0;
    int right = nums.Length - 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;
}

// Print the index of the target
// Your code here

Hint

Use Console.WriteLine(Search(nums, target)); to print the index.

Practice

1. What is the main challenge when searching in a rotated sorted array compared to a normal sorted array?

easy

A. The array is sorted in descending order instead of ascending

B. The array contains duplicate elements that confuse the search

C. The array is split into two sorted parts, making normal binary search invalid directly

D. The array size is always odd, which affects indexing

Solution

1. Step 1: Understand the array structure

   A rotated sorted array is created by taking a sorted array and rotating it at some pivot. This splits it into two sorted parts.

2. Step 2: Why normal binary search fails

   Normal binary search assumes the entire array is sorted. Here, because of rotation, one half is sorted and the other may not be, so direct binary search won't work.

3. Final Answer:

   The array is split into two sorted parts, making normal binary search invalid directly -> Option C

4. Quick Check:

   Rotation splits array = challenge for binary search [OK]

Hint: Look for the pivot splitting the array into two sorted parts [OK]

Common Mistakes:

• Assuming the whole array is sorted
• Ignoring the pivot point
• Confusing rotation with reversal

2. Which of the following C# code snippets correctly initializes variables for binary search in a rotated sorted array?

easy

A. int left = -1, right = nums.Length - 1;

B. int left = 1, right = nums.Length;

C. int left = 0, right = nums.Length;

D. int left = 0, right = nums.Length - 1;

Solution

1. Step 1: Understand array indexing in C#

   Arrays are zero-indexed, so the first element is at 0 and the last at Length - 1.

2. Step 2: Correct initialization for binary search

   Binary search starts with left at 0 and right at last index (Length - 1). This covers the entire array.

3. Final Answer:

   int left = 0, right = nums.Length - 1; -> Option D

4. Quick Check:

   Zero-based indexing means right = Length - 1 [OK]

Hint: Start left at 0 and right at last index (Length - 1) [OK]

Common Mistakes:

• Setting right to Length instead of Length - 1
• Starting left at 1 instead of 0
• Using negative indices

3. What will be the output of the following C# code snippet searching for target 3 in rotated array int[] nums = {4,5,6,7,0,1,2};?

int left = 0, right = nums.Length - 1;
int target = 3;
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;

medium

A. -1

B. 6

C. 0

D. 4

Solution

1. Step 1: Understand the array and target

   The array is rotated: [4,5,6,7,0,1,2]. Target is 3, which is not in the array.

2. Step 2: Trace the binary search steps

   Binary search checks mid and adjusts left/right. Since 3 is not present, loop ends and returns -1.

3. Final Answer:

   -1 -> Option A

4. Quick Check:

   Target missing returns -1 [OK]

Hint: If target not found, binary search returns -1 [OK]

Common Mistakes:

• Assuming target 3 is in array
• Returning wrong index for missing target
• Not updating left/right correctly

4. Identify the bug in this C# code snippet for searching target in rotated sorted array:

int left = 0, right = nums.Length - 1;
while (left < right) {
    int mid = (left + right) / 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;

medium

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

B. Mid calculation should be mid = left + (right - left) / 2

C. The target comparison operators are incorrect

D. The return -1 should be inside the loop

Solution

1. Step 1: Analyze loop condition

   The loop uses left < right, which misses the case when left == right, possibly skipping the last element check.

2. Step 2: Correct loop condition for binary search

   Binary search requires left <= right to ensure all elements are checked, including when left equals right.

3. Final Answer:

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

4. Quick Check:

   Use left <= right for complete search [OK]

Hint: Use <= in loop condition to check all elements [OK]

Common Mistakes:

• Using < instead of <= in loop
• Incorrect mid calculation causing overflow
• Misplaced return statements

5. Given a rotated sorted array int[] nums = {15, 18, 2, 3, 6, 12};, write a C# method to find the index of target 3 using binary search in rotated array. What is the returned index?

hard

A. 2

B. 3

C. 4

D. -1

Solution

1. Step 1: Understand the array and target

   The array is rotated: [15, 18, 2, 3, 6, 12]. Target is 3, which is present at index 3.

2. Step 2: Apply binary search in rotated array

   Using the binary search logic for rotated arrays, the search will find target 3 at index 3.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   Target 3 found at index 3 [OK]

Hint: Trace mid and adjust left/right to find target index [OK]

Common Mistakes:

• Confusing index of 3 with nearby elements
• Not handling rotation correctly
• Returning -1 for existing target