Binary search after determining if the array is left-rotated or right-rotated
mid = (left + right ) // 2
Left-rotated -> arr[mid] > arr[left]:
3-1. if nums[left] <= target < nums[mid] reset right index right = mid - 1
3-2. Else, left = mid + 1
Right-rotated -> arr[mid] < arr[left]
4-1. If nums[mid] < target and target <= nums[right], reset left index left = mid + 1
4-2. Else, right = mid - 1
"""
Binary Search
nums = [3,4,5,6,0,1,2], target = 3
"""
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
# If the current number is larger than the target, move the window
"""
Determine if the array is left rotated or right rotated
Original
1 2 3 4 5
mid
Left-rotated -> arr[mid] > arr[left]
2 3 4 5 1
mid
Right-rotated -> arr[mid] < arr[left]
5 1 2 3 4
mid
"""
# The array is left rotated
if nums[mid] >= nums[left]:
# If the target number is in between the left side of the array, reset right index to continue search on the left side
if nums[left] <= target and target < nums[mid]:
right = mid - 1
else:
left = mid + 1
# The array is right rotated
else:
# If the target number is in between the right side of the array, reset left index to continue search on the right side
if nums[mid] < target and target <= nums[right]:
left = mid + 1
else:
right = mid - 1
# If not in the array
return -1
33. Search in Rotated Sorted Array
https://leetcode.com/problems/search-in-rotated-sorted-array/description/
mid = (left + right ) // 2arr[mid] > arr[left]: 3-1. ifnums[left] <= target < nums[mid]reset right indexright = mid - 13-2. Else,left = mid + 1arr[mid] < arr[left]4-1. Ifnums[mid] < target and target <= nums[right], reset left indexleft = mid + 14-2. Else,right = mid - 1n: length of the array
O(log(n))binary searchO(1)no extra space used