For this problem, in every iteration of binary search, we need to make sure next pivot falls into the correct segment.
Given we have mid as pivot index, the status of array falls into either of two cases:
A. nums[left:mid] is consistently increasing
B. nums[mid:right] is consistently increasing
(if both are true, array is not rotated at all, we can treat it as case A )
For case A, target can only be in the right side of the pivot in following two cases:
- Every number in nums[left:mid] is bigger than target (we check if nums[left] is bigger than target)
- Every number in nums[left:mid] is smaller than target (we check if nums[mid] is smaller than target)
else: target MUST be in the left side of the pivot, we go ahead and search left
For case B, we use the same logic.
class Solution(object): def search(self, nums, target): left, right = 0, len(nums)-1 while right >= left: mid = (left+right)/2 if nums[mid] == target: return mid # if nums[left:mid] is increasing if nums[mid] >= nums[left]: if nums[left] > target or nums[mid] <= target: left = mid + 1 else: right = mid - 1 # if nums[mid:right] is increasing else: if nums[right] < target or nums[mid] >= target: right = mid - 1 else: left = mid + 1 return -1