Search in Rotated Sorted Array in DSA C# - Execution Trace

Concept Flow - Search in Rotated Sorted Array

Start with full array

↓

Find middle element

↓

Check if middle is target?

↓

Return

↓

Left half sorted

↓

Check if target in left half?

↓

Search left

↓

Repeat steps with new range

↓

Not found -> return -1

We repeatedly check the middle element, decide which half is sorted, and narrow search to the half where the target can be.

Execution Sample

DSA C#

int Search(int[] nums, int target) {
  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;
}

This code searches for target in a rotated sorted array by narrowing the search range based on sorted halves.

Execution Table

Step	Operation	Left	Right	Mid	nums[Mid]	Check	Action	Search Range	Result
1	Initialize	0	6	-	-	-	Start search	[0..6]	-
2	Calculate mid	0	6	3	7	nums[mid] == target? 7 == 0	No	[0..6]	-
3	Check left half sorted	0	6	3	7	nums[left] <= nums[mid]? 4 <= 7	Yes	[0..6]	-
4	Check target in left half	0	6	3	7	4 <= 0 < 7?	No	[0..6]	-
5	Update left	4	6	-	-	-	left = mid + 1	[4..6]	-
6	Calculate mid	4	6	5	0	nums[mid] == target? 0 == 0	Yes	[4..6]	Return 5
7	End	-	-	-	-	-	-	-	Index 5 found

💡 Target found at index 5, search ends.

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 6	Final
left	0	0	4	4	4
right	6	6	6	6	6
mid	-	3	3	5	5
nums[mid]	-	7	7	0	0
Search Range	[0..6]	[0..6]	[4..6]	[4..6]	[4..6]

Key Moments - 3 Insights

Why do we check if the left half is sorted using nums[left] <= nums[mid]?

Because in a rotated sorted array, one half is always sorted. Checking nums[left] <= nums[mid] tells us if the left half is sorted. See execution_table step 3.

Why do we update left to mid + 1 when target is not in the left sorted half?

If target is not in the sorted half, we search the other half by moving left or right pointers. In step 5, since target is not in left half, left moves to mid + 1.

What happens if the target is not found in the array?

The while loop ends when left > right, and the function returns -1 indicating target not found. This is not shown in this example but is the exit condition.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what does the condition nums[left] <= nums[mid] evaluate to?

A Equals target

B True

C False

D Undefined

💡 Hint

Check the 'Check' column at step 3 in execution_table.

At which step does the search range update to [4..6]?

A Step 2

B Step 4

C Step 5

D Step 6

💡 Hint

Look at the 'Search Range' and 'Action' columns in execution_table.

If the target was 3 instead of 0, what would be the result after step 6?

A Return -1

B Return index 5

C Continue searching left half

D Return index 3

💡 Hint

Consider that nums[5] is 0, not 3, so target not found at step 6.

Concept Snapshot

Search in Rotated Sorted Array:
- Use binary search with left, right, mid pointers
- Check which half is sorted by comparing nums[left] and nums[mid]
- Narrow search to half where target can be
- Repeat until target found or range invalid
- Return index or -1 if not found

Full Transcript

This concept shows how to search a target value in a rotated sorted array using a modified binary search. We start with the full array and find the middle element. If the middle element is the target, we return its index. Otherwise, we check which half of the array is sorted by comparing the left and middle elements. Depending on which half is sorted and whether the target lies within that half, we adjust the search range to either the left or right half. We repeat this process until we find the target or the search range becomes invalid, returning -1 if not found. The execution table traces each step with variable values and decisions, helping visualize how the search narrows down. Key moments clarify why we check sorted halves and how pointers move. The visual quiz tests understanding of conditions and pointer updates.

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