Search in Rotated Sorted Array in DSA Go

Mental Model

We want to find a number in a list that was sorted but then rotated. We use a smart search that checks which part is sorted to decide where to look next.

Analogy: Imagine a clock face with numbers 1 to 12 in order. If you rotate the clock so 3 is at the top, the numbers are still in order but start from 3. To find a number, you check if it is in the part before or after the top and search there.

Original sorted array:
[1] -> [2] -> [3] -> [4] -> [5] -> [6] -> [7] -> null

Rotated array (rotated at 4):
[4] -> [5] -> [6] -> [7] -> [1] -> [2] -> [3] -> null

Dry Run Walkthrough

Input: array: [4,5,6,7,0,1,2], target: 0

Goal: Find the index of target 0 in the rotated sorted array

Step 1: Set left=0, right=6, find mid=(0+6)/2=3

[4] -> [5] -> [6] -> [7] -> [0] -> [1] -> [2]
left=0, mid=3, right=6

Why: We start searching in the whole array by checking the middle element

Step 2: Check if left to mid is sorted: 4 ≤ 7 is true

[4] -> [5] -> [6] -> [7] -> [0] -> [1] -> [2]
left to mid sorted

Why: Knowing which half is sorted helps decide where to search next

Step 3: Check if target 0 is between left(4) and mid(7): no

[4] -> [5] -> [6] -> [7] -> [0] -> [1] -> [2]

Why: Target is not in the sorted left half, so search right half

Step 4: Set left=mid+1=4, right=6, find mid=(4+6)/2=5

[4] -> [5] -> [6] -> [7] -> [0] -> [1] -> [2]
left=4, mid=5, right=6

Why: Focus search on right half where target may be

Step 5: Check if left to mid is sorted: 0 ≤ 1 is true

[4] -> [5] -> [6] -> [7] -> [0] -> [1] -> [2]
left to mid sorted

Why: Again find which half is sorted to decide search

Step 6: Check if target 0 is between left(0) and mid(1): yes

[4] -> [5] -> [6] -> [7] -> [0] -> [1] -> [2]

Why: Target is in sorted left half, so search there

Step 7: Set right=mid-1=4, left=4, find mid=(4+4)/2=4

[4] -> [5] -> [6] -> [7] -> [0] -> [1] -> [2]
left=4, mid=4, right=4

Why: Narrow down search to smaller range

Step 8: Check if nums[mid]=0 equals target 0: yes, found at index 4

[4] -> [5] -> [6] -> [7] -> [0] -> [1] -> [2]

Why: Target found, stop searching

Result:

[4] -> [5] -> [6] -> [7] -> [0] -> [1] -> [2]
Target 0 found at index 4

Annotated Code

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
        }
        // Check if left half is sorted
        if nums[left] <= nums[mid] {
            // Check if target is in left half
            if nums[left] <= target && target < nums[mid] {
                right = mid - 1
            } else {
                left = mid + 1
            }
        } else {
            // Right half is sorted
            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
    index := search(nums, target)
    if index != -1 {
        fmt.Printf("Target %d found at index %d\n", target, index)
    } else {
        fmt.Printf("Target %d not found\n", target)
    }
}

for left <= right {

loop to narrow search range until left passes right

mid := (left + right) / 2

find middle index to check

if nums[mid] == target { return mid }

if middle element is target, return index

if nums[left] <= nums[mid] {

check if left half is sorted

if nums[left] <= target && target < nums[mid] { right = mid - 1 } else { left = mid + 1 }

decide to search left half or right half based on target position

else { if nums[mid] < target && target <= nums[right] { left = mid + 1 } else { right = mid - 1 } }

if right half is sorted, decide where to search

Output

Target 0 found at index 4

Complexity Analysis

Time: O(log n) because each step halves the search range by checking sorted halves

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Compared to linear search O(n), this binary search approach is much faster on large arrays

Edge Cases

empty array

returns -1 immediately because left > right

DSA Go

for left <= right {

array with one element matching target

returns index 0 immediately

DSA Go

if nums[mid] == target { return mid }

target not in array

returns -1 after search range is exhausted

DSA Go

return -1

When to Use This Pattern

When you see a sorted array that has been rotated and need to find an element quickly, use this pattern of checking which half is sorted to guide binary search.

Common Mistakes

Mistake: Not checking which half is sorted before deciding where to search
Fix: Always check if left to mid is sorted or else right to mid is sorted to decide search direction

Mistake: Using <= or < incorrectly causing infinite loops
Fix: Use correct comparison operators and update left or right pointers properly to shrink search range

Summary

Finds target index in a rotated sorted array using modified binary search.

Use when searching in arrays sorted but rotated at some pivot.

Key insight: one half of the array is always sorted, use that to decide search direction.

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