Search in rotated sorted array II
September 5, 2022
binary-searchProblem URL: Search in rotated sorted array II
To solve this problem we have to follow the folllowing steps:
- Calculate the mid index.
- Check if the mid element == target, return True else move to next step.
- Else if the mid element >= left. If mid element >= target and and left <= target, then shift right to mid-1 position, else shift left to mid+1 position.
- If target >= mid element and target <=right, then shift left to mid+1 position, else shift right to mid-1 position.
- If the element is not found return False
Note: Since duplicate elemnts are present in the array so remove all the duplicates before step 1.
class Solution:
def search(self, nums: List[int], target: int) -> bool:
if len(nums) == 1:
if nums[0] == target:
return True
return False
l, r = 0, len(nums)-1
while l <= r:
# shifting to remove duplicate elements
while l<r and nums[l] == nums[l+1]:
l += 1
while l<r and nums[r] == nums[r-1]:
r -= 1
# step 1 calculate the mid
mid=(l+r)//2
# step 2
if nums[mid] == target:
return True
# step 3
elif nums[l] <= nums[mid]:
if nums[mid]>=target and nums[l]<=target:
r = mid-1
else:
l = mid+1
# step 4
else:
if nums[mid]<=target and nums[r]>=target:
l = mid+1
else:
r = mid-1
# step 5
return False
Time Complexity: O(log(n))
Space Complexity: O(1)