Recall valid inputs such as

[0 1 2 4 5 6 7]

[4 5 6 7 8 9 0 1 2]

- Loop invariant: closed searching interval [low, high] must include target if it exists.
- Input may be ascending or ascending-drop-ascending. For either case, if nums[mid] <= nums[-1] (last element), right half is ordered, else left half is ordered.
- Ordered half enables constant-time check for whether target is in the ordered half ("nums[low] <= target < nums[mid]" or "nums[mid] < target <= nums[high]") or the other unordered half. Hence binary search is possible.

Follow-up:

- Search in Rotated Sorted Array II

What if duplicates are allowed?

My follow-up explanations:

https://discuss.leetcode.com/topic/61987/clear-explanations-for-efficient-solution

```
class Solution(object):
def search(self, nums, target):
low = 0
high = len(nums) - 1
while low <= high:
mid = (high - low) / 2 + low
if nums[mid] == target:
return mid
else:
# Right half is ascending.
if nums[mid] <= nums[-1]:
# Target is in right half.
if nums[mid] < target <= nums[high]:
low = mid + 1
# Target is in left half.
else:
high = mid - 1
# Left half is ascending.
else:
# Target is in left half.
if nums[low] <= target < nums[mid]:
high = mid - 1
# Target is in right half.
else:
low = mid + 1
return -1
```