这一题其实就是二分查找，于是就比较简单，但是我的代码并不好，

我的思路是首先利用二分找到旋转的那个节点，然后在其节点的左边还是右边进行旋转；

第一步进行二分查找，我的代码就进行了很多不必要的操作；

我的第一步查找，是根据，左边是否比右边小，如果不是，则返回这个旋转的节点；

class Solution {
public:

	array<int, 3> find_point(vector<int>&nums, int lo, int hi)
	{
		if (lo == hi)  return array<int, 3>{lo, lo, 0};
		int mi = lo + (hi - lo) / 2;
		array<int, 3> left = find_point(nums, lo, mi);
		array<int, 3> right = find_point(nums, mi + 1, hi);
		if (left[2] == 1) return array<int, 3>{left[0], left[1], 1};
		if (right[2] == 1) return array<int, 3>{right[0], right[1], 1};
		if (nums[left[1]] < nums[right[0]])    return array<int, 3>{left[0], right[1], 0};
		else return array<int, 3>{left[1], left[1], 1};
	}


	int find(vector<int>&nums, int lo, int hi, int target)
	{
		if (lo == hi) {
			if (target == nums[lo])    return lo;
			else return -1;
		}
		int mi = lo + (hi - lo) / 2;
		if (target <= nums[mi]&&target>=nums[lo]) return find(nums, lo, mi, target);
		else return find(nums, mi + 1, hi, target);
	}


	int search(vector<int>& nums, int target) {
        if(nums.empty()) return -1;
		array<int, 3> cut_point = find_point(nums, 0, nums.size() - 1);
        if (cut_point[2] == 0)	return find(nums, 0, nums.size() - 1, target);
		if (target <= nums[cut_point[0]]&&target>=nums[0]) return find(nums, 0, cut_point[0], target);
		else return find(nums, cut_point[0] + 1, nums.size() - 1, target);
	}
};

，于是我看了别人的另种解法：这里我就不解释了；直接贴上别人的解释，我觉得，他直接在搜索的时候，就判断左边是否是升序的数组，如果不是，则说明，这里面含有旋转的节点，然后在通过比较target是否在里面，来进行缩小区间去查找，这样就一步到位：

注意到原数组为有限制的有序数组（除了在某个点会突然下降外均为升序数组）

if nums[0] <= nums[I] 那么 nums[0] 到 nums[i] 为有序数组,那么当 nums[0] <= target <= nums[i] 时我们应该在 0-i0−i 范围内查找；

if nums[i] < nums[0] 那么在 0-i0−i 区间的某个点处发生了下降（旋转），那么 I+1I+1 到最后一个数字的区间为有序数组，并且所有的数字都是小于 nums[0] 且大于 nums[i]，当target不属于 nums[0] 到 nums[i] 时（target <= nums[i] < nums[0] or nums[i] < nums[0] <= target），我们应该在 0-i0−i 区间内查找。
上述三种情况可以总结如下：

    nums[0] <= target <= nums[i]
               target <= nums[i] < nums[0]
                         nums[i] < nums[0] <= target
所以我们进行三项判断：

(nums[0] <= target)， (target <= nums[i]) ，(nums[i] < nums[0])，现在我们想知道这三项中有哪两项为真（明显这三项不可能均为真或均为假（因为这三项可能已经包含了所有情况））

所以我们现在只需要区别出这三项中有两项为真还是只有一项为真。

使用 “异或” 操作可以轻松的得到上述结果（两项为真时异或结果为假，一项为真时异或结果为真，可以画真值表进行验证）

之后我们通过二分查找不断做小 target 可能位于的区间直到 low==high，此时如果 nums[low]==target 则找到了，如果不等则说明该数组里没有此项。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int lo = 0, hi = nums.size() - 1;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if ((nums[0] > target) ^ (nums[0] > nums[mid]) ^ (target > nums[mid]))
                lo = mid + 1;
            else
                hi = mid;
        }
        return lo == hi && nums[lo] == target ? lo : -1;
    }
};