153. Find Minimum in Rotated Sorted Array

Overview of the Approach

This method employs a binary search strategy tailored for a rotated sorted array, where the primary goal is to identify the minimum element. Unlike a standard binary search that seeks a specific value, this approach focuses on understanding the array's rotation to locate the smallest element.

Intuition and Strategy:

The approach hinges on comparing the middle element (mid) to the rightmost element (right). This comparison determines which part of the array is sorted and thus where the minimum might be:

• If mid is greater than right, the minimum is further right, so we move the left boundary rightward.
• If mid is less than or equal to right, the minimum could be at mid or to its left, so we move the right boundary leftward.

Updating the 'Right' Value:

Properly updating the right pointer is crucial. Unlike standard binary search, where we'd exclude mid in the next search, here, mid could be the minimum, so we set right to mid. This ensures we don't miss the smallest element.

Focusing on Boundaries:

The algorithm narrows the search space each iteration by adjusting boundaries instead of seeking an exact match. The condition left < right ensures the search continues until the pointers converge, pinpointing the minimum element.

In essence, this adapted binary search method efficiently narrows down the location of the minimum element in a rotated sorted array by continuously adjusting the search boundaries based on comparisons between the middle and rightmost elements.

Solution

Version1: Using left < right

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

    while (left < right) {
        let mid = left + (right-left)/2
        if nums[right] < nums[mid] {
            left = mid+1
        } else {
            right = mid
        }
    }
    
    return nums[left]
}

Version2: Using left <= right and a result variable

func findMin(_ nums: [Int]) -> Int {
    var left = 0, right = nums.count-1
    var result = nums[0]

    while (left <= right) {
        if nums[left] < nums[right] {
            result = min(result, nums[left])
            break
        }

        let mid = left + (right-left)/2
        result = min(result, nums[mid])

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

    return result
}

Complexities

• Time Complexity: O(log N)
• Space Complexity: O(1)