find-minimum-in-rotated-sorted-array.go

// https://leetcode.com/problems/find-minimum-in-rotated-sorted-array

func findMin(nums []int) int {
    n := len(nums)
    i, j := 0, n
    minItem := (1 << 31) - 1
    
    for i < j {
        h := (i + j) >> 1
        
        if nums[i] < nums[h] {
            // [i, h] is sorted, we can check the first item for min
            minItem = min(nums[i], minItem)
            
            if nums[h] > nums[n - 1] {
                // we found pivot
                i = h + 1
            } else {
                j = h
            }
        } else {
            if nums[h] <= nums[n - 1] {
                // [h, n - 1] is sorted, we can check the median item for min
                minItem = min(nums[h], minItem)
                j = h
            } else {
                i = h + 1
            }
        }
    }
    
    return minItem
}

func min(a, b int) int {
    if a < b {
        return a
    }
    
    return b
}