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.