33. Search in Rotated Sorted Arr

题目描述：一个排好序的序列在某个值处翻转了，如0 1 2 4 5 6 7变为 4 5 6 7 0 1 2。序列中的数无重复，在这个翻转后的序列中查找目标值并返回下标，没找到则返回-1。

分析：有序序列中查找值可用二分法，现在在某个值处旋转后，则变为两段有序序列。用二分的思想，若目标值所在数据段不包含断点则按原二分法即可；若包含断点则范围也可缩小。故一层条件判断断点所在段，每层中继续判断目标值所在段，共4种情况，找例子分析即可得到不同情况取哪段。总之目标值是在一段有序序列中。时间复杂度O(lgn)，空间O(1)。

代码：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size();
        while(l != r)
        {
            int mid = (l + r) / 2;
            if (nums[mid] == target)
                return mid;
            //首先分为l ~ mid, mid ~ r两段，由于不知道断点在哪段故分条件处理
            if (nums[l] <= nums[mid])     //断点不在l ~ mid
            {
                if (nums[l] <= target && target < nums[mid])          //目标值在l ~ mid
                    r = mid;
                else        //目标值不在l ~ mid
                    l = mid + 1;
            }
            else           //断点在l ~ mid，则mid ~ r无断点
            {
                if (nums[mid] < target && target <= nums[r - 1])                   //目标值在mid ~ r
                    l = mid + 1;
                else                //目标值不在mid ~ r
                    r = mid;
            }
        }
        return -1;
    }
};