传送门
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。
示例 1:
输入: nums = [4,5,6,7,0,1,2], target = 0 输出: 4示例 2:
输入: nums = [4,5,6,7,0,1,2], target = 3 输出: -1参考题解1和题解2 时间复杂度是 O ( l o g ( n ) ) O(log(n)) O(log(n))， 空间复杂度 O ( 1 ) O(1) O(1), 执行用时： 40 m s 40 ms 40ms
二分思想
查找的target不是反转的某个点，以及处理好边界值，输入为空或单个值
反转的节点的前后两部分是各自有序的，mid位置索引的值和target会有几种情况
举例：
4 5 6 7 8 0 1 2 3
mid 若在4-8之间的一个索引，对于target的值有三种情况
向前半部分寻找向后半部分寻找 n u m s [ i ] < t a r g e t < n u m s [ m i d ] nums[i]<target<nums[mid] nums[i]<target<nums[mid] n u m s [ i ] < n u m s [ m i d ] < t a r g e t nums[i]<nums[mid]<target nums[i]<nums[mid]<target t a r g e t < n u m s [ i ] target<nums[i] target<nums[i]mid 若在0-3之间的一个索引，对于target的值有三种情况
向前半部分寻找向后半部分寻找 n u m s [ m i d ] < n u m s [ i ] > t a r g e t nums[mid]<nums[i]>target nums[mid]<nums[i]>target n u m s [ m i d ] < t a r g e t < n u m s [ i ] nums[mid]<target<nums[i] nums[mid]<target<nums[i] t a r g e t < n u m s [ m i d ] < n u m s [ i ] target<nums[mid]<nums[i] target<nums[mid]<nums[i]