Search in Rotated Sorted Array in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of search in rotated sorted array

What is the output of the following Go code that searches for a target in a rotated sorted array?

DSA Go

package main
import "fmt"

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
}

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

A 4

B 0

C -1

D 6

💡 Hint

Remember the array is rotated; the target 0 is not at the start.

The target 0 is at index 4 in the rotated array [4,5,6,7,0,1,2]. The binary search correctly finds it and returns 4.

❓ Predict Output

intermediate

Output when target is not in rotated array

What is the output of this Go code searching for a target not present in the rotated sorted array?

DSA Go

package main
import "fmt"

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
}

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

A 6

B 3

C 0

D -1

💡 Hint

Target 3 is not in the array.

Since 3 is not in the array, the function returns -1 indicating not found.

🔧 Debug

advanced

Identify the error in rotated array search code

What error will this Go code produce when searching in a rotated sorted array?

DSA Go

package main
import "fmt"

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
            }
        }
    }
    if nums[left] == target {
        return left
    }
    return -1
}

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

A Returns -1 incorrectly

B Infinite loop occurs

C Returns correct index 4

D Compilation error due to missing colon

💡 Hint

Check the loop condition and boundary checks carefully.

The loop condition 'left < right' misses the case when left == right, causing the target at that position to be missed sometimes, leading to incorrect -1 return.

🧠 Conceptual

advanced

Why binary search works on rotated sorted arrays

Why can binary search be adapted to find an element in a rotated sorted array?

A Because the array elements are all unique, so linear search is faster

B Because the array is fully sorted, so normal binary search applies directly

C Because one half of the array is always sorted, allowing elimination of half the search space

D Because the rotation does not change the array length

💡 Hint

Think about how the array is split after rotation.

In a rotated sorted array, at least one half (left or right) is sorted. This property allows binary search to decide which half to discard, maintaining O(log n) time.

🚀 Application

expert

Find minimum element index in rotated sorted array

Given a rotated sorted array with unique elements, which code snippet correctly finds the index of the minimum element?

A

left, right := 0, len(nums)-1
for left <= right {
    mid := (left + right) / 2
    if nums[mid] < nums[left] {
        right = mid - 1
    } else {
        left = mid + 1
    }
}
return right

B

left, right := 0, len(nums)-1
for left < right {
    mid := (left + right) / 2
    if nums[mid] > nums[right] {
        left = mid + 1
    } else {
        right = mid
    }
}
return left

C

left, right := 0, len(nums)-1
for left < right {
    mid := (left + right) / 2
    if nums[mid] < nums[left] {
        right = mid
    } else {
        left = mid + 1
    }
}
return left

D

left, right := 0, len(nums)-1
for left <= right {
    mid := (left + right) / 2
    if nums[mid] > nums[left] {
        left = mid + 1
    } else {
        right = mid - 1
    }
}
return left

💡 Hint

The minimum element is the only element smaller than its previous element in the rotated array.

Option B correctly uses binary search to find the smallest element by comparing mid with right, narrowing the search space until left points to the minimum.

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