Related: Find Minimum in Rotated Sorted Array
Intuition
- The key to understanding this question is to imagine “mid” or target falling off the edge. But, mid or target could be anywhere on the two halves of the split, so simply simulate the 4 possibilities for which half mid and target are on, respectively when doing binary search.
- i.e. nums[mid] < nums[left] and target < nums[left] means that you are on the right half, there is a split, and you need to find if target < nums[mid] or target > nums[mid] and recurse on that side.
Takeway
- When solving problems like these, similar to Interval type problems, there will be a lot of if statements. Be very verbose with the if statements which will help you debug quickly, then condense your answer only when you have verified that the verbose version works.
- I first attempted this problem by trying to find out where the pivot was, but quickly found many edge cases due to the nature of binary search in that for the case of the array of size 1 or 2, one can not check the next element.
Runtime
- due to one passthrough of binary search.
Code
Elegant
class Solution:
def search(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums) - 1
while left <= right:
mid = (left + right) // 2
if target == nums[mid]:
return mid
if target < nums[left] and nums[mid] >= nums[left]:
left = mid + 1
elif target >= nums[left] and nums[mid] < nums[left]:
right = mid - 1
else:
if target < nums[mid]:
right = mid - 1
elif target > nums[mid]:
left = mid + 1
return -1Verbose
class Solution:
def search(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums) - 1
while left <= right:
mid = (left + right) // 2
if target == nums[mid]:
return mid
if target < nums[left] and nums[mid] < nums[left]:
if target < nums[mid]:
right = mid - 1
elif target > nums[mid]:
left = mid + 1
elif target < nums[left] and nums[mid] >= nums[left]:
left = mid + 1
elif target >= nums[left] and nums[mid] < nums[left]:
right = mid - 1
elif target >= nums[left] and nums[mid] >= nums[left]:
if target < nums[mid]:
right = mid - 1
elif target > nums[mid]:
left = mid + 1
else:
print("HOUSTON")
return -1