33. 搜索旋转排序数组

二分法

class Solution {
    func search(_ nums: [Int], _ target: Int) -> Int {
        if nums.isEmpty {
            return -1
        }
        if nums.count == 1 {
            return (nums[0] == target) ? 0 : -1
        }

        var left = 0
        var right = nums.count - 1
        
        // left <= right 说明相遇了 在变就错过
        while left <= right { 
            // 确定中间值
            let mid = (right - left) / 2 + left
            if nums[mid] == target {
                return mid
            }
            // nums[mid] < nums[right] 说明 mid 右边是有序递增的
            if nums[mid] < nums[right] {
                //如果 target 值在这个有序递增的范围内那就能确定 left 了，这里包含了右边等于 target 值的情况
                if target > nums[mid], target <= nums[right] {
                    left = mid + 1
                } else {
                    right = mid - 1
                }
            } else { // nums[mid] > nums[right]  说明突变值（最小值）在 mid 右边，则 mid 左边是有序递增的
                if target >= nums[left], target < nums[mid] {
                    //如果 target 值在这个有序递增的范围内那就能确定 right 了，这里包含了左边等于 target 值的情况
                    right = mid - 1
                } else {
                    left = mid + 1
                }
            }
        }
        return -1
    }
}