33. Search in Rotated Sorted Array

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

无重复递增数组从某个点开始把后面元素全部按原来的序移到前面，找target所在位置，没有则返回-1。二分，根据nums[mid]和nums[0]以及target和nums[mid]大小比较共有四种情况。先根据target和nums[0]分成两种不以mid所在位置决定的静态情况。分别对这两种情况套用lower_bound，考虑什么时候start 一定要前移到mid + 1：target >= nums[0]时，mid落在[nums[0], target)；otherwise, mid落在[target, nums[0])外。

/*
 * @lc app=leetcode id=33 lang=cpp
 *
 * [33] Search in Rotated Sorted Array
 */

// @lc code=start
class Solution {
public:
    int search(vector<int>& nums, int target) {
        if (nums.size() == 0) return -1;
        int start = 0, end = nums.size() - 1;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (target >= nums[0]) {
                if (nums[mid] >= nums[0] && nums[mid] < target) start = mid + 1;
                else end = mid;
            } else {
                if (!(nums[mid] < nums[0] && nums[mid] >= target)) start = mid + 1;
                else end = mid;
            }
        } 
        return nums[start] == target ? start : -1; 
    }
};
// @lc code=end