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.