Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
题意分析：
本题是将一个排好序的数组从某一个（不清楚为什么原题中是some pivot，但是肯定是一个，因为如果是多个，考虑极端情况数组将会变成完全是无序的）位置进行旋转，也就是说将一个本来严格递增的数组变成了前后两部分递增的序列，所以会有一个分界。在这样一个旋转后的数组里面查找数字，并返回它的下标，如果找不到的话返回-1。
解答：
如果是个普通的递增数组，那么直接用二分查找就ok了。本题并不是一个严格递增的序列，但是仍然可以用二分查找去做。
二分查找的核心是取两端元素的中间节点mid，本题可以在获取了mid之后和两端元素对比。如果左边元素小于mid，那么mid一定是落在了右面的递增序列中；反之一定是落在了左边。target是要查找的值，知道了mid在哪边之后，就可以拿边界值和target做对比得到两种特殊情况：
- 落在右端时，如果target大于右端最大值，那么要查找的一定在左端；
- 落在左端时，如果target小于左端最小值，那么要查找的一定在右端。
除去这两种特殊情况之后，直接简单的用二分查找进行处理就可以了。
AC代码：
class Solution(object):
def search(self, nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) / 2
if nums[mid] == target:
return mid
# mid in the right side of rotated sorted array
if nums[left] > nums[mid]:
# target can't be in the right side
if target > nums[right]:
right = mid - 1
else:
# simple binary search
if nums[mid] > target:
right = mid - 1
else:
left = mid + 1
# mid in the left side of rotated sorted array
else:
# target can't be in the left side
if target < nums[left]:
left = mid + 1
else:
if nums[mid] > target:
right = mid - 1
else:
left = mid + 1
return -1