First, we need to know whether the array has been rotated. Then we can just do standard binary search, except that we need to have clear ideas where the target falls into. Say the prerotated order is a,b,c,d and we have c,d,a,b afterwards. we can be more selective by not only comparing target with elements at mid indices, but also c and b which are low and high repectively. This way we can distinguish case by case where target and mid fall into (it's either in (a,b) or (c,d)).
def search(self, nums, target): if not nums: return -1 if nums[-1] >= nums: ret = bisect.bisect_left(nums, target) return ret if 0 <= ret < len(nums) and nums[ret] == target else -1 lo, hi = 0, len(nums) - 1 while lo <= hi: mid = (lo + hi) >> 1 if nums[mid] == target: return mid elif nums[mid] < target: if nums[hi] == target: return hi elif nums[hi] > target: lo = mid + 1 else: if nums[mid] <= nums[hi]: hi = mid - 1 else: lo = mid + 1 else: if nums[hi] == target: return hi elif nums[hi] < target: hi = mid -1 else: if nums[mid] <= nums[hi]: hi = mid - 1 else: lo = mid + 1 return -1