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.

Practice

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

easy

A. The array size is unknown

B. The array contains duplicate elements

C. The array is unsorted

D. The array is split into two sorted parts, making direct binary search tricky

Solution

1. Step 1: Understand the array structure

   A rotated sorted array is originally sorted but then rotated at some pivot, splitting it into two sorted parts.

2. Step 2: Identify the search challenge

   Because of the rotation, a simple binary search cannot be applied directly as the array is not fully sorted in one sequence.

3. Final Answer:

   The array is split into two sorted parts, making direct binary search tricky -> Option D

4. Quick Check:

   Rotation splits array = search challenge [OK]

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

Common Mistakes:

• Assuming the array is fully sorted
• Ignoring the rotation pivot
• Trying linear search only

2. Which of the following Go function signatures correctly represents a binary search in a rotated sorted array?

easy

A. func search(nums []int, target int) int

B. func search(nums int, target int) int

C. func search(nums []int, target string) int

D. func search(nums []int, target int) bool

Solution

1. Step 1: Check parameter types

   The function should accept a slice of integers and an integer target to search for.

2. Step 2: Check return type

   The function returns an integer index of the target or -1 if not found, so return type int is correct.

3. Final Answer:

   func search(nums []int, target int) int -> Option A

4. Quick Check:

   Correct params and return type = func search(nums []int, target int) int [OK]

Hint: Function takes []int and int target, returns int index [OK]

Common Mistakes:

• Using wrong parameter types
• Returning bool instead of index
• Using string target instead of int

3. What is the output of the following Go code snippet?

nums := []int{4,5,6,7,0,1,2}
target := 0
fmt.Println(search(nums, target))

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
}

medium

A. -1

B. 0

C. 4

D. 6

Solution

1. Step 1: Identify target and array

   Target is 0, array is rotated sorted: [4,5,6,7,0,1,2].

2. Step 2: Trace binary search steps

   Mid starts at index 3 (value 7), target 0 is not equal. Left half [4..7] is sorted. Target 0 is not in left half, so move left to mid+1=4. Now left=4, right=6. Mid=5 (value 1). Target 0 < 1, right=mid-1=4. Now left=4, right=4. Mid=4 (value 0), found target at index 4.

3. Final Answer:

   4 -> Option C

4. Quick Check:

   Target 0 found at index 4 [OK]

Hint: Check mid, decide which half is sorted, adjust search [OK]

Common Mistakes:

• Not updating left/right correctly
• Confusing sorted half
• Returning wrong index

4. The following Go code attempts to search a target in a rotated sorted array but has a bug. What is the bug?

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
}

medium

A. The function does not return the index

B. The loop condition should be 'left <= right' instead of 'left < right'

C. The target comparison uses wrong operators

D. The mid calculation is incorrect

Solution

1. Step 1: Analyze loop condition

   The loop uses 'left < right', which stops when left == right, possibly missing the last element check.

2. Step 2: Correct loop condition

   Changing to 'left <= right' ensures the last element is checked, preventing missed target.

3. Final Answer:

   The loop condition should be 'left <= right' instead of 'left < right' -> Option B

4. Quick Check:

   Loop must include equal to check [OK]

Hint: Use 'left <= right' to cover all elements in binary search [OK]

Common Mistakes:

• Using 'left < right' and missing last element
• Incorrect mid calculation
• Wrong comparison operators

5. Given a rotated sorted array with possible duplicates, which modification is needed in the binary search to correctly find the target?

nums := []int{2,5,6,0,0,1,2}
target := 0

hard

A. Add extra checks to skip duplicates when nums[left] == nums[mid] == nums[right]

B. Use linear search instead of binary search

C. Ignore duplicates and apply normal rotated binary search

D. Sort the array before searching

Solution

1. Step 1: Understand duplicates effect

   Duplicates can cause ambiguity in deciding which half is sorted when nums[left] == nums[mid] == nums[right].

2. Step 2: Modify search to skip duplicates

   When duplicates appear at left, mid, and right, increment left and decrement right to skip duplicates and continue search.

3. Final Answer:

   Add extra checks to skip duplicates when nums[left] == nums[mid] == nums[right] -> Option A

4. Quick Check:

   Skip duplicates to avoid ambiguity [OK]

Hint: Skip duplicates at edges when equal to mid [OK]

Common Mistakes:

• Ignoring duplicates causing wrong half detection
• Switching to linear search unnecessarily
• Sorting array breaks problem constraints