arcbjorn

thoughtbook

Saturday, February 25, 2023

Find minimum in rotated sorted array

Leetcode 153 problem.

Go

  • Time complexity: O(log(n))O(log(n)) - n is a length of an array
  • Auxiliary space: O(1)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]
}
Creative Commons Licence