thoughtbook

Saturday, February 25, 2023

Find minimum in rotated sorted array

Leetcode 153 problem.

Go

Time complexity: $O(log(n))$ - n is a length of an array
Auxiliary space: $O(1)$ - constant amount of space

func findMin(nums []int) int {
    left, right := 0, len(nums) - 1

    for left < right {
        mid := left + (right - left) / 2

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