Search in Rotated Sorted Array in DSA Go - Build from Scratch

Search in Rotated Sorted Array

📖 Scenario: Imagine you have a list of numbers that was originally sorted but then rotated at some unknown point. You want to find if a specific number exists in this rotated list.

🎯 Goal: You will write a Go program that searches for a target number in a rotated sorted array using an efficient method.

📋 What You'll Learn

Create a slice called nums with the exact values [4, 5, 6, 7, 0, 1, 2]

Create an integer variable called target and set it to 0

Write a function called search that takes nums []int and target int and returns the index of target in nums or -1 if not found

Use binary search logic adapted for rotated sorted arrays inside the search function

Print the result of calling search(nums, target)

💡 Why This Matters

🌍 Real World

Rotated sorted arrays appear in systems where data is cyclically shifted, such as time-based logs or circular buffers. Efficient search helps quickly find needed information.

💼 Career

Understanding how to search in rotated sorted arrays is useful for software engineers working on performance-critical applications, embedded systems, or interview coding challenges.

1

Create the rotated sorted array

Create a slice called nums with the exact values [4, 5, 6, 7, 0, 1, 2]

DSA Go

# Create the slice nums with values [4, 5, 6, 7, 0, 1, 2]
// Your code here

Hint

Use nums := []int{4, 5, 6, 7, 0, 1, 2} to create the slice.

2

Set the target number to search

Create an integer variable called target and set it to 0

DSA Go

package main

func main() {
    nums := []int{4, 5, 6, 7, 0, 1, 2}
    // Create target variable and set it to 0
    // Your code here
}

Hint

Use target := 0 to create the variable.

3

Write the search function using binary search logic

Write a function called search that takes nums []int and target int and returns the index of target in nums or -1 if not found. Use binary search logic adapted for rotated sorted arrays inside the search function.

DSA Go

package main

func search(nums []int, target int) int {
    // Your code here
}

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

Hint

Use a loop with left, right, and mid pointers. Check which side is sorted and adjust left and right accordingly.

4

Print the search result

Print the result of calling search(nums, target) inside the main function.

DSA Go

package main

func search(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right-left)/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
    // Print the index of target in nums
    // Your code here
}

Hint

Use fmt.Println(search(nums, target)) to print the result.