剑指 Offer 11. 旋转数组的最小数字 - 简单

剑指 Offer 11. 旋转数组的最小数字

二分法

• 时间复杂度
  O(log n) 在二分查找的过程中，大部分情况都会忽略一半的区间。
• 空间复杂度
  O(1)

func minArray(_ numbers: [Int]) -> Int {
        if numbers.count == 1 {
            return numbers[0]
        }
        var left = 0
        var right = numbers.count - 1
        while right > left {
            let mid = (right - left) / 2 + left
            if numbers[mid] > numbers[right] {
                // numbers[mid] > numbers[right] mid 已经大于 right 所以 mid 不应该包含在区间内  所以 mid + 1
                left = mid + 1
            } else if numbers[mid] < numbers[right] {
                right = mid
            } else {
                //  mid 和 left right 相等的情况， 就让right -=1
                right -= 1
            }
        }
        return numbers[left]
    }

一次遍历法

• 时间复杂度
  O(n)
• 空间复杂度
  O(1)

func minArray(_ numbers: [Int]) -> Int {
        if numbers.isEmpty {
            return -1
        }
        var ans = numbers[0]
        for item in numbers {
            ans = min(ans, item)
        }
        return ans
    }