search-in-rotated-sorted-array
Last updated
Was this helpful?
Last updated
Was this helpful?
This problem asked to implement in O(logn)
. Binary search should come into your mind when you see O(logn)
, sorted and search keywords.
Intuitive solution is simple, iterate through array, find target in nums return pos, not, return -1, O(n)
Binary search, given array is rotated sorted array, meaning there are 2 sorted array. when do binary search, need to carefully compare
target and nums[mid] and nums[lo] to chose whether go right (higher) or left (lower).
define lo, hi, and mid = (lo + hi)/2
.
if target == nums[mid]
found, return mid and exit.
if nums[mid] >= nums[lo]
meaning mid is within sorted parts, now compare target,
if target >= nums[lo] && target <= nums[md]
, target is located in [lo, mid]
sorted part, search left, hi = mid - 1
else target located in [mid, hi]
, search right, lo = mid + 1
else check compare target with hi and mid value
if target >= nums[mid] && target <= nums[hi]
, target is located in [mid, hi]
part, search right, lo = mid + 1
else target located in [lo, mid]
part, search left, hi = mid - 1
For example:
Time Complexity: O(log(N))
Space Complexity: O(1)
N - the length of array nums
Naive solution - O(n)