LeetCode 33. Search in Rotated Sorted Array

题目：https://leetcode.com/problems/search-in-rotated-sorted-array/
思路：
有序数列里头找元素，第一想到的肯定是二分法，但是现在数组的一部分被旋转过了，这怎么改进呢？假定输入是[4 5 6 7 0 1 2]，如果仍用二分法，那么第一次搜索时，左中右的元素分别是a[left] = 4; a[mid]=7; a[right]=2
从题设可以知道，问题的关键是，被拆分的两个部分里，肯定是一半有序一半无序的(因为旋转点，即a[i+1] > a[i]的i点)肯定只能在两部分的其一里头，而对于有序的那一半，我们可以通过首末元素判断target是否在其中，于是有了下面的规则：

• 观察被二分出来的左半段（当然右半段也可以），根据a[left],a[mid]的值判断这半段是否有序
  • 如果有序，根据头尾元素判断target是否在里头，如果在，那就搜索左半端，否则只能在无序的右半段里找了
  • 如果无序，那右半段肯定是有序的，去判断target是否在右半段里头：如果在，则搜索右半段，否则还是老老实实把左半端再二分了找吧..

想比普通的二分，这个方法多了几个判断的步骤，但整体的时间复杂度还是O(logN)
代码：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        int mid;
        while(left <= right){
            mid = (left + right) / 2;
            if(target == nums[mid])
                return mid;
            if(nums[left] <= nums[mid]){
                //The left part is in order, check if target is inside
                if(nums[left] <= target && nums[mid] >= target){
                    //Yep, move to the left part
                    right = mid - 1;
                } else {
                    //Nope, move to the right part
                    left = mid + 1;
                }
            } else {
                //The left part is not in order, but the right one should be, check if target is in the right wing
                if(nums[mid] <= target && nums[right] >= target){
                    //Yep, move to the right wing
                    left = mid + 1;
                } else {
                    //Nope, try in the left wing
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
};