33. 搜索旋转排序数组
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。
示例 1:
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
示例 2:
输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1
Python most votes solution with some revision:
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo+hi) // 2
if nums[mid] == target:
return mid
if nums[0] <= target < nums[mid] or target < nums[mid] < nums[0] or nums[mid] < nums[0] <= target:
hi = mid - 1
else:
lo = mid + 1
return -1
解析：
GitHub上给出的原始解释：https://leetcode.com/problems/search-in-rotated-sorted-array/discuss/14419/Pretty-short-C%2B%2BJavaRubyPython
这个解释不够直观，一种直观的解释如下图所示：
上图中线段的高度代表了数字的大小：高度越高，代表的数字越大。其中第0个数字nums[0]已用特殊的柱形表示。
正如上图所示，如果目标数字target在nums中，那么它要么在第I区段，要么在第II区段（除此之外没有第三种情况）。
mid 被定义为：mid = (lo + hi) // 2
对于上图所示的情形而言，假设target位于第I区段，即nums[0] <= target，则：
（1）假设nums[mid] 位于第II区段，则为了让nums[mid]找到target，必须想办法让nums[mid]往左移动，这样才能让nums[mid]接近target，如何做到这一点呢？
注意到mid的定义：mid = (lo + hi) // 2，假设我们减小hi（在二分查找算法中，lo永远只会增加，hi永远只会减小），则mid将变小，从而在上图中将会向左移（如图中红色虚线所指向的方向），这样便有可能会找到target；
这种情况总结为：当nums[mid] < nums[0] <= target时，mid左移。
（2）假设nums[mid]位于第I区段，因为不清楚nums[mid]是在target的左边还是右边，因此要分情况考虑：
a）假设nums[mid]在target的左边，则希望nums[mid]右移；
b）假设nums[mid]在target的右边，则希望nums[mid]左移。
这种情况总结为：
当nums[0] <= nums[mid] <= target时，mid右移；
当nums[0] <= target <= nums[mid]时，mid左移。
类似地，假设target位于第II区段，则可总结出如下情况：
当target < nums[0] <= nums[mid] 时，mid右移；
当target <= nums[mid] < nums[0]时，mid左移；
当nums[mid] <= target < nums[0]时，mid右移。
在讨论完以上所有情况后，挑出希望mid左移的情形，汇总如下：
nums[0] <= target < nums[mid] or target < nums[mid] < nums[0] or nums[mid] < nums[0] <= target
因此就有了程序中的if...else...的判断语句：
if nums[0] <= target < nums[mid] or target < nums[mid] < nums[0] or nums[mid] < nums[0] <= target:
hi = mid - 1
else:
lo = mid + 1
这里为什么还要让mid - 1和mid + 1，然后再赋给hi和lo？考虑如下情况：
假如mid要右移，此时mid = 5，hi = 6，若lo = mid，则新的mid = (lo + hi) // 2 = (5 + 6) // 2 = 5，和原来的mid相比，新的mid值不变，此时mid将永远陷在mid = 5 的位置，从而造成死循环。而lo = mid + 1可以解决这种死循环的问题。hi = mid - 1也是同样的道理。