Search in Rotated Sorted Array in DSA Go - Execution Trace

Concept Flow - Search in Rotated Sorted Array

Start with full array

↓

Find middle element

↓

Check if middle is target?

↓

Return index

↓

Is left half sorted?

↓

Is target in left half?

↓

Search left half

↓

Repeat until found or empty

↓

Return -1 if not found

The search splits the array by middle, checks which half is sorted, and decides where to continue searching until the target is found or array is empty.

Execution Sample

DSA Go

func search(nums []int, target int) int {
  left, right := 0, len(nums)-1
  for left <= right {
    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 a target in a rotated sorted array using a modified binary search.

Execution Table

Step	Operation	Left	Mid	Right	nums[Left]	nums[Mid]	nums[Right]	Target	Decision	New Left	New Right	Visual State
1	Initialize pointers	0	4	8	4	0	4	0	Check nums[mid] == target? No	0	8	[4,5,6,7,0,1,2,3,4]
2	Check if left half sorted	0	4	8	4	0	4	0	nums[left] <= nums[mid]? No	0	4	[4,5,6,7,0,1,2,3,4]
3	Check if target in right half	0	4	8	4	0	4	0	nums[mid] < target <= nums[right]? 0 < 0 <= 4? No	0	3	[4,5,6,7,0,1,2,3,4]
4	Search left half	0	4	3	4	0	4	0	Update right = mid - 1	0	3	[4,5,6,7,0,1,2,3,4]
5	Calculate new mid	0	1	3	4	5	4	0	Check nums[mid] == target? No	0	3	[4,5,6,7,0,1,2,3,4]
6	Check if left half sorted	0	1	3	4	5	4	0	nums[left] <= nums[mid]? Yes	0	3	[4,5,6,7,0,1,2,3,4]
7	Check if target in left half	0	1	3	4	5	4	0	nums[left] <= target < nums[mid]? 4 <= 0 < 5? No	2	3	[4,5,6,7,0,1,2,3,4]
8	Search right half	2	3	3	6	7	4	0	Update left = mid + 1	4	3	[4,5,6,7,0,1,2,3,4]
9	Check loop condition	4	-	3	-	-	-	0	left > right, exit loop	4	3	[4,5,6,7,0,1,2,3,4]
10	Return -1	-	-	-	-	-	-	0	Target not found	-	-	[4,5,6,7,0,1,2,3,4]

💡 left (4) > right (3), so target not found, return -1

Variable Tracker

Variable	Start	After Step 1	After Step 4	After Step 5	After Step 8	Final
left	0	0	0	0	4	4
right	8	8	3	3	3	3
mid	4	4	1	1	3	-

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 2 and 6).

Why do we update left or right pointers based on target's position relative to nums[left], nums[mid], and nums[right]?

We decide which half to search next by checking if the target lies within the sorted half's range. This narrows the search space correctly (see execution_table steps 7 and 8).

What causes the loop to end without finding the target?

When left pointer becomes greater than right pointer (step 9), it means the target is not in the array, so we return -1 (step 10).

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the value of nums[mid]?

A 5

B 0

C 7

D 3

💡 Hint

Check the 'nums[Mid]' column at step 6 in the execution_table.

At which step does the left pointer become greater than the right pointer, causing the loop to exit?

A Step 8

B Step 9

C Step 10

D Step 7

💡 Hint

Look at the 'Decision' and 'Operation' columns in steps 8 and 9 in the execution_table.

If the target was 7 instead of 0, which pointer would be updated at step 8?

A left pointer would be updated

B right pointer would be updated

C both pointers would be updated

D no pointer would be updated

💡 Hint

Refer to the logic in execution_table steps 6-8 and how pointers change based on target position.

Concept Snapshot

Search in Rotated Sorted Array:
- Use modified binary search
- Check middle element against target
- Determine which half is sorted
- Narrow search to half containing target
- Repeat until found or empty
- Return index or -1 if not found

Full Transcript

This visual trace shows how to search a target in a rotated sorted array using a modified binary search. We start with left and right pointers at the array ends. We find the middle element and check if it matches the target. If not, we check which half of the array is sorted by comparing nums[left] and nums[mid]. Depending on which half is sorted and where the target lies, we update left or right pointers to narrow the search. This repeats until the target is found or the pointers cross, meaning the target is not present. The execution table tracks each step's pointers, values, and decisions. The variable tracker shows how left, right, and mid pointers change. Key moments clarify why we check sorted halves and how pointer updates work. The quiz tests understanding of pointer values and loop exit conditions. This method efficiently finds the target in O(log n) time even if the array is rotated.