81. 搜索旋转排序数组 II - 中等

81. 搜索旋转排序数组 II

二分法

• 时间复杂度
  O(n) 大多情况下每次都减少一般的数据

• 空间复杂度
  O(1)

  func search(_ nums: [Int], _ target: Int) -> Bool {
        if nums.isEmpty {
            return false
        }
        if nums.count == 1 {
            return nums[0] == target
        }
        var left = 0
        var right = nums.count - 1
        // [1, 2]
        // 必须是 >= 会存在 到最后左右指针相遇 才找到 目标值的情况
        while right >= left {
            let mid = (right - left) / 2 + left
            if nums[mid] == target {
                return true
            }
            if nums[mid] < nums[right] {
                if nums[mid] < target, target <= nums[right] {
                    left = mid + 1
                } else {
                    right = mid - 1
                }
            } else if nums[mid] > nums[right] {
                if nums[left] <= target, target < nums[mid] {
                    right = mid - 1
                } else {
                    left = mid + 1
                }
            } else {
                right -= 1
            }
        }
  
        return false
    }