一、题目
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [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
二、解答
2.1 方法一：二分查找
2.1.1 思路
题目要找到一种 O(logN) 时间内的搜索方法，这提示我们可以用二分查找的方法。
算法非常直接：
找到旋转的下标，也就是数组中最小的元素。二分查找在这里可以派上用场。
在选中的数组区域中再次使用二分查找。
public static int search(int[] nums, int target) {
if(nums.length == 0){
return -1;
}
int min = nums[0];
int l = 0;
int r = nums.length - 1;
//获取最小元素下标与值
while (l < r){
int mid = (l+r)/2;
//mid+1、mid-1的值均大于mid的值，则mid为最小元素
if (nums[mid] <= nums[mid + 1 > nums.length - 1 ? nums.length - 1 : mid + 1]
&& nums[mid] <= nums[mid - 1 < 0 ? 0 : mid - 1]){
l = mid;
break;
//有旋转的情况一：mid大于右边，则元素在右边
}else if (nums[mid] > nums[r]){
l = mid+1;
//有旋转的情况二：mid小于左边，则元素在左边
}else if (nums[mid] < nums[l]){
r = mid-1;
//无旋转的情况一：mid小于右边，则元素在左边
}else if(nums[mid] < nums[r]){
r = mid-1;
//无旋转的情况二：nums[mid] > nums[l],则元素在左边
}else {
l = mid+1;
}
}
//获取最小值
min = Math.min(min,nums[l]);
//获取元素所在的l与r,且此时是nums[l] ~ nums[r]是递增数组
if (target >= min && target <= nums[nums.length - 1]){
r = nums.length - 1;
}else {
r = l - 1;
l = 0;
}
//递增数组，采用二分查找获取元素
while (l<=r){
int mid = (l+r)/2;
if (target == nums[mid]){
return mid;
}else if (target >nums[mid]){
l = mid + 1;
}else {
r = mid - 1;
}
}
return -1;
}
2.2 方法二：二分查找+大神操作
2.2.1 思路
以二分搜索为基本思路
简要来说：
nums[0] <= nums[mid]（0 - mid不包含旋转）且nums[0] <= target <= nums[mid] 时 high 向前规约；
nums[mid] < nums[0]（0 - mid包含旋转），target <= nums[mid] < nums[0] 时向前规约（target 在旋转位置到 mid 之间）
nums[mid] < nums[0]，nums[mid] < nums[0] <= target 时向前规约（target 在 0 到旋转位置之间）
其他情况向后规约
也就是说nums[mid] < nums[0]，nums[0] > target，target > nums[mid] 三项均为真或者只有一项为真时向后规约。
原文的分析是：
注意到原数组为有限制的有序数组（除了在某个点会突然下降外均为升序数组）
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 则找到了，如果不等则说明该数组里没有此项。
2.2.2 实现
public static int search1(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while (l < r) {
int mid = (l + r) / 2;
if ((nums[0] > target) ^ (nums[0] > nums[mid]) ^ (target > nums[mid]))
l = mid + 1;
else
r = mid;
}
return l == r && nums[l] == target ? l : -1;
}
