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

Concept Flow - Search in Rotated Sorted Array

Start: Given rotated sorted array and target

↓

Initialize low=0, high=n-1

↓

While low <= high

↓

Calculate mid = (low+high)/2

↓

Check if arr[mid

↓

Return mid

↓

If left half sorted

↓

Target in left?

↓

high=mid-1

↓

Repeat loop

↓

If not found

↓

Return -1

This flow shows how binary search adapts to a rotated sorted array by checking sorted halves and narrowing search.

Execution Sample

DSA C++

int search(vector<int>& nums, int target) {
  int low = 0, high = nums.size() - 1;
  while (low <= high) {
    int mid = low + (high - low) / 2;
    if (nums[mid] == target) return mid;
    if (nums[low] <= nums[mid]) {
      if (nums[low] <= target && target < nums[mid]) high = mid - 1;
      else low = mid + 1;
    } else {
      if (nums[mid] < target && target <= nums[high]) low = mid + 1;
      else high = mid - 1;
    }
  }
  return -1;
}

This code searches for target in a rotated sorted array using modified binary search.

Execution Table

Step	Operation	low	mid	high	Condition Checked	Pointer Changes	Visual State
1	Initialize pointers	0	-	6	-	-	[4,5,6,7,0,1,2]
2	Calculate mid	0	3	6	nums[mid]=7 != target=0	-	[4,5,6,7,0,1,2]
3	Check left half sorted	0	3	6	nums[low]=4 <= nums[mid]=7 (True)	-	[4,5,6,7,0,1,2]
4	Check if target in left half	0	3	6	4 <= 0 < 7 (False)	low = mid + 1 = 4	[4,5,6,7,0,1,2]
5	Calculate mid	4	5	6	nums[mid]=1 != target=0	-	[4,5,6,7,0,1,2]
6	Check left half sorted	4	5	6	nums[low]=0 <= nums[mid]=1 (True)	-	[4,5,6,7,0,1,2]
7	Check if target in left half	4	5	6	0 <= 0 < 1 (True)	high = mid - 1 = 4	[4,5,6,7,0,1,2]
8	Calculate mid	4	4	4	nums[mid]=0 == target=0	-	[4,5,6,7,0,1,2]
9	Target found	4	4	4	Return mid=4	-	[4,5,6,7,0,1,2]

💡 Target found at index 4, loop ends.

Variable Tracker

Variable	Start	After Step 4	After Step 7	After Step 8	Final
low	0	4	4	4	4
high	6	6	4	4	4
mid	-	3	5	4	4

Key Moments - 3 Insights

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

Because in a rotated sorted array, one half is always sorted. Checking nums[low] <= nums[mid] tells us if the left half is sorted, so we know where to search next (see steps 3 and 6 in execution_table).

Why do we update low or high based on whether the target lies within the sorted half?

If the target is inside the sorted half, we narrow the search to that half by updating low or high accordingly. Otherwise, we search the other half. This logic is shown in steps 4 and 7.

Why do we calculate mid as (low + high) / 2 each iteration?

Because binary search splits the search space in half each time. Updating mid after changing low or high ensures we check the middle of the current search range (see steps 2, 5, and 8).

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'mid' at step 6?

A 5

B 3

C 4

D 6

💡 Hint

Check the 'mid' column in execution_table row with Step 6.

At which step does the condition nums[mid] == target become true?

A Step 4

B Step 8

C Step 7

D Step 9

💡 Hint

Look for the step where 'Condition Checked' column shows equality in execution_table.

If the target was 3 instead of 0, what would happen to the 'low' pointer after step 4?

A It would remain 0

B It would become 4

C It would become 3

D It would become 6

💡 Hint

Check step 4's 'Pointer Changes' and think if target=3 fits in the left half range.

Concept Snapshot

Search in Rotated Sorted Array:
- Use binary search with low, high pointers
- Calculate mid = (low+high)/2
- Check if left half (low to mid) is sorted
- If target in sorted half, narrow search there
- Else search other half
- Repeat until found or low > high
- Return index or -1 if not found

Full Transcript

This concept shows how to find a target number in a rotated sorted array using a modified binary search. We start with two pointers, low and high, at the ends of the array. We find the middle index mid and check if the middle element is the target. If not, we check which half of the array is sorted. If the left half is sorted and the target lies within it, we move the high pointer to mid-1 to search left. Otherwise, we move low to mid+1 to search right. If the right half is sorted, we do the opposite. We repeat this process until we find the target or the pointers cross, meaning the target is not in the array. This method efficiently handles the rotation by always searching the sorted half. The execution table traces each step with pointer values and conditions checked, showing how the search narrows down to the target index.