Search in Rotated Sorted Array
- 2 min read
- LC-Medium
- Binary-search
3 years ago
Solution
- Future Faaez, you might be super-confused about this problem if you're coming at in randomly, here's what you do:
- Chill, you already understood this
- Understand Find Minimum in Rotated Sorted Array, this problem builds on top of that
- Watch both NeetCode videos
- Do a dry run on Example 1
- An important concept in this problem is knowing whether or not we're in the left or right sorted portion of the array. This will help us manager our pointers
- If we're in the left portion, we just need to see if our target is within the bounds. If it is not, move to the right sorted portion. We can easily check if it's in bounds using the left and right bounds of the leftmost sorted portion of the array, i.e. nums[l] and nums[mid]
- Basically, let's say we're in the first iteration of Example 1
- left is at 4, mid is at 7, right is at 2.
- When checking the left portion, if our target falls out of these bounds, we need to recur right.
- Else, we need to recur left, ie. search within our left sorted portion.
- Just do a dry run-- you'll understand
- If we're in the left portion, we just need to see if our target is within the bounds. If it is not, move to the right sorted portion. We can easily check if it's in bounds using the left and right bounds of the leftmost sorted portion of the array, i.e. nums[l] and nums[mid]
- There's really no use typing the algorithm- either understand the code or watch the neetcode video on this topic. Cheers
| Time | Space | Explanation |
|---|---|---|
O() | O() |
def search(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums) - 1
while l <= r:
mid = (l + r) // 2
if nums[mid] == target:
return mid
# if we are in left sorted portion of array, check if target is in bounds
if nums[mid] >= nums[l]:
if target < nums[l] or target > nums[mid]:
l = mid + 1
else:
r = mid - 1
# if we are in right sorted portion of array, check if target is in bounds
else:
if target < nums[mid] or target > nums[r]:
r = mid - 1
else:
l = mid + 1
return -1