LeetCode Blind 75 in Swift: Solving the "Search in Rotated Sorted Array" Problem

Problem: Search in Rotated Sorted Array

The Search in Rotated Sorted Array problem asks you to search for a target value in a rotated sorted array of unique integers. If the target exists, return its index. If not, return -1.

Example:

Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0
Output: 4
        

Swift Solution

class Solution {
    func search(_ nums: [Int], _ target: Int) -> Int {
        var left = 0
        var right = nums.count - 1

        while left <= right {
            let mid = (left + right) / 2
            if nums[mid] == target {
                return mid
            }
            
            // Determine which part is sorted
            if nums[left] <= nums[mid] {
                // Left side is sorted
                if target >= nums[left] && target < nums[mid] {
                    right = mid - 1
                } else {
                    left = mid + 1
                }
            } else {
                // Right side is sorted
                if target > nums[mid] && target <= nums[right] {
                    left = mid + 1
                } else {
                    right = mid - 1
                }
            }
        }
        
        return -1
    }
}

let solution = Solution()
let nums = [4, 5, 6, 7, 0, 1, 2]
let target = 0
let result = solution.search(nums, target)
print(result) // Output: 4
        

Explanation

This solution applies a binary search with a slight modification to account for the rotation. By checking which side of the array is sorted, we can determine which half of the array to search next. We repeatedly narrow down the search range until we either find the target or conclude it doesn't exist.