Search in Rotated Sorted Array - Go Solution

LeetCode

— 1 min read

Solving the LeetCode "Search in Rotated Sorted Array" Problem in Go

Difficulty: Medium | Tags: Array, Binary Search

Introduction

The "Search in Rotated Sorted Array" problem requires finding the index of a target value in a rotated sorted array with O(log n) time complexity. This problem tests understanding of binary search and array manipulation.

Problem Analysis

Given a sorted array that has been rotated at an unknown pivot, we need to efficiently locate a target value. For example, in the array [4,5,6,7,0,1,2], the target 0 is located at index 4. If the target is not present, we return -1.

Solution Approach

The solution involves a modified binary search. We first determine which half of the array is sorted by comparing the middle element with the leftmost element. Based on this, we adjust the search range to the sorted half if the target lies within it, otherwise, we search the other half.

Go Implementation


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
        }
        // Check if the left half is sorted
        if nums[left] <= nums[mid] {
            // Check if the target is in the left half
            if nums[left] <= target && target < nums[mid] {
                right = mid - 1
            } else {
                left = mid + 1
            }
        } else {
            // Check if the target is in the right half
            if nums[mid] < target && target <= nums[right] {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
    }
    return -1
}

Complexity Analysis

The algorithm runs in O(log n) time because it uses binary search to halve the search space in each iteration. The space complexity is O(1) as no additional space is used beyond a few variables.

Testing and Examples

Test cases include:
1. nums = [4,5,6,7,0,1,2], target = 0 → Output: 4
2. nums = [4,5,6,7,0,1,2], target = 3 → Output: -1
3. nums = [1], target = 0 → Output: -1
Edge cases: single-element array, target at the first or last index.

Best Practices and Tips

Key takeaways include ensuring the correct comparison of mid and left elements to determine the sorted half, and carefully adjusting the search range. Always verify edge cases, such as empty arrays or targets outside the array bounds.

Read more