There is an integer array nums
sorted in non-decreasing order (not necessarily with distinct values).
Before being passed to your function, nums
is rotated at an unknown pivot index k
(0 <= k < nums.length
) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]
(0-indexed). For example, [0,1,2,4,4,4,5,6,6,7]
might be rotated at pivot index 5
and become [4,5,6,6,7,0,1,2,4,4]
.
Given the array nums
after the rotation and an integer target
, return true
if target
is in nums
, or false
if it is not in nums
.
You must decrease the overall operation steps as much as possible.
Example 1:
Input: nums = [2,5,6,0,0,1,2], target = 0 Output: true
Example 2:
Input: nums = [2,5,6,0,0,1,2], target = 3 Output: false
Constraints:
1 <= nums.length <= 5000
-104 <= nums[i] <= 104
nums
is guaranteed to be rotated at some pivot.-104 <= target <= 104
Solution: Binary search or divide and conquer
If current range is ordered, use binary search, Otherwise, divide and conquer.
Time complexity: O(logn) best, O(n) worst
Space complexity: O(logn)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua class Solution { public: bool search(vector<int>& A, int target) { return search(A, 0, A.size() - 1, target); } private: bool search(vector<int>& A, int l, int r, int target) { if (l > r) return 0; if (l == r) return target == A[l]; int mid = l + (r - l) / 2; if (A[l] < A[mid] && A[mid] < A[r]) return (target <= A[mid]) ? search(A, l, mid, target) : search(A, mid + 1, r, target); else return search(A, l, mid, target) || search(A, mid + 1, r, target); } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment