LC 33. Search in Rotated Sorted Array

https://leetcode.com/problems/search-in-rotated-sorted-array/

说来这题也没有什么特别的技巧，但是情况容易考虑不全面，所以我在这里整理一下。 在旋转有序数组上进行二分搜索，我们需要在原来的二分搜索算法上做些改进。

一个有序数组旋转之后，样子大致是这样的

   2
  t
 1
s
          e
        5
      m
     3

如果nums[m]<target的话，默认情况下是去高部分查找，也就是 `s=m+1`, 但是对于上图我们就需要去 低部分查找，也就是 `e=m-1`.

那么如何概括上图那个情况呢？我这里给出的条件是

1. nums[s] >= nums[e]
2. nums[s] <= target
3. nums[m] <= nums[e]
4. nums[m] < target

所以总结起来就是 `nums[m] <= nums[e] <= nums[s] <= target`.

对于nums[m]>target的话，可以得到几乎相同的条件表达是 `target <= nums[e] <= nums[s] <= nums[m]`.

def search(self, nums: List[int], target: int) -> int:
    s, e = 0, len(nums) - 1
    while s <= e:
        m = (s + e) // 2
        if nums[m] == target:
            return m
        if nums[m] > target:
            if target <= nums[e] <= nums[s] <= nums[m]:
                s = m + 1
            else:
                e = m - 1
        else:
            if nums[m] <= nums[e] <= nums[s] <= target:
                e = m - 1
            else:
                s = m + 1
    return -1