Search in Rotated Sorted Array in DSA C#

Mental Model

We want to find a number in a list that was sorted but then rotated, by smartly checking halves instead of scanning all.

Analogy: Imagine a clock face where numbers are in order but the clock is turned so 12 is not at the top. To find a number, you check if it's in the left or right half by comparing with the middle, like checking which side of the clock the number is on.

Array: [4, 5, 6, 7, 0, 1, 2]
Indexes:  0  1  2  3  4  5  6
Pointers: ↑           ↑
           left       right
Middle:          ↑

Dry Run Walkthrough

Input: array: [4, 5, 6, 7, 0, 1, 2], target: 0

Goal: Find the index of target 0 in the rotated sorted array

Step 1: Calculate middle index between left=0 and right=6, middle=3

[4, 5, 6, 7, 0, 1, 2]
 left=0 -> 4, middle=3 -> 7, right=6 -> 2

Why: We check the middle to decide which half to search next

Step 2: Check if left half [4,5,6,7] is sorted by comparing nums[left]=4 and nums[middle]=7

[4, 5, 6, 7, 0, 1, 2]
 left half sorted: 4 ≤ 7 is true

Why: Knowing which half is sorted helps decide where target could be

Step 3: Check if target=0 lies between left=4 and middle=7

Target 0 not in range 4 to 7

Why: Since target is not in sorted left half, search right half next

Step 4: Move left pointer to middle+1=4 to search right half

[4, 5, 6, 7, 0, 1, 2]
 left=4 -> 0, right=6 -> 2

Why: Focus search on right half where target may be

Step 5: Calculate middle index between left=4 and right=6, middle=5

[4, 5, 6, 7, 0, 1, 2]
 left=4 -> 0, middle=5 -> 1, right=6 -> 2

Why: Check middle of new search range

Step 6: Check if left half [0,1] is sorted by comparing nums[left]=0 and nums[middle]=1

Left half sorted: 0 ≤ 1 is true

Why: Identify sorted half to decide where target lies

Step 7: Check if target=0 lies between left=0 and middle=1

Target 0 is in range 0 to 1

Why: Target is in sorted left half, so search there

Step 8: Move right pointer to mid-1=4 to narrow search to left half

[4, 5, 6, 7, 0, 1, 2]
 left=4 -> 0, right=4 -> 0

Why: Narrow search to left half where target is

Step 9: Calculate middle index between left=4 and right=4, middle=4

[4, 5, 6, 7, 0, 1, 2]
 left=4 -> 0, middle=4 -> 0, right=4 -> 0

Why: Check middle element in narrowed range

Step 10: Check if nums[middle]=0 equals target=0

Found target at index 4

Why: Target found, return index

Result:

[4, 5, 6, 7, 0, 1, 2]
Target 0 found at index 4

Annotated Code

DSA C#

using System;

class RotatedSortedArraySearch
{
    public static int Search(int[] nums, int target)
    {
        int left = 0, right = nums.Length - 1;
        while (left <= right)
        {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target)
                return mid; // found target

            if (nums[left] <= nums[mid]) // left half sorted
            {
                if (nums[left] <= target && target < nums[mid])
                    right = mid - 1; // target in left half
                else
                    left = mid + 1; // target in right half
            }
            else // right half sorted
            {
                if (nums[mid] < target && target <= nums[right])
                    left = mid + 1; // target in right half
                else
                    right = mid - 1; // target in left half
            }
        }
        return -1; // target not found
    }

    static void Main()
    {
        int[] nums = {4, 5, 6, 7, 0, 1, 2};
        int target = 0;
        int index = Search(nums, target);
        if (index != -1)
            Console.WriteLine($"Target {target} found at index {index}");
        else
            Console.WriteLine($"Target {target} not found");
    }
}

int mid = left + (right - left) / 2;

Calculate middle index to split search range

if (nums[mid] == target) return mid;

Check if middle element is target

if (nums[left] <= nums[mid])

Check if left half is sorted

if (nums[left] <= target && target < nums[mid]) right = mid - 1;

If target in sorted left half, move right pointer

else left = mid + 1;

Else search right half

else

Right half must be sorted

if (nums[mid] < target && target <= nums[right]) left = mid + 1;

If target in sorted right half, move left pointer

else right = mid - 1;

Else search left half

Output

Target 0 found at index 4

Complexity Analysis

Time: O(log n) because each step halves the search range

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

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

Edge Cases

Empty array

Returns -1 immediately as no elements to search

DSA C#

int right = nums.Length - 1;

Array with one element equal to target

Returns index 0 immediately

DSA C#

if (nums[mid] == target) return mid;

Array with one element not equal to target

Returns -1 after checking single element

DSA C#

while (left <= right)

Target not in array

Returns -1 after search completes

DSA C#

return -1;

When to Use This Pattern

When you see a sorted array that is rotated and need to find an element quickly, use this modified binary search to identify sorted halves and narrow search efficiently.

Common Mistakes

Mistake: Not checking which half is sorted before deciding where to search next
Fix: Always compare nums[left] and nums[mid] to find sorted half before moving pointers

Mistake: Using <= or < incorrectly causing infinite loops or missed targets
Fix: Use consistent comparison operators to correctly include or exclude mid element in ranges

Summary

Finds target index in a rotated sorted array using modified binary search.

Use when array is sorted but rotated and you want fast search.

Key insight: one half is always sorted, use that to decide where target lies.

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