class Solution {
public int search(int[] nums
, int target
) {
int left
= 0,right
= nums
.length
- 1;
int pos
= -1;
while(left
< right
){
int mid
= (left
+ right
) / 2;
if(mid
== left
){
break;
}
if(nums
[mid
] == target
){
pos
= mid
;
break;
}
if(nums
[left
] < nums
[mid
]){
if(nums
[left
] <= target
&& nums
[mid
] >= target
)right
= mid
;
else
left
= mid
;
continue;
}
else if(nums
[mid
] < nums
[right
]){
if(nums
[mid
] <= target
&& nums
[right
] >= target
)left
= mid
;
else
right
= mid
;
continue;
}
}
if(pos
== -1){
if(nums
[left
] == target
)pos
= left
;
else if(nums
[right
] == target
)pos
= right
;
}
return pos
;
}
}
解题的思路基于一个事实，即将数组等分之后，至少有一侧是有序的，以下面的图来说明：
(绿线表示左侧的最小值要大于右侧的最大值)
数组划分不外乎这三种情况，可以看到每一种划分都至少有一侧是有序的。
求解步骤：
1、找到数组划分之后有序的那一半（例如nums[left] < nums[mid]，则说明左侧有序）,判断有序的这一侧的取值是否涵盖了target（例如，如果左侧是有序的，则判断是否有nums[left] <= target <= nums[mid]） 2、（以左侧有序为例），如果nums[left] <= target <= nums[mid]成立，那么target只可能存在于左侧，因为右侧的取值范围是小于nums[left]或者大于nums[mid]（参照图片中的绿线，并且注意nums无重复元素），这时就在左侧按正常的二分法来做 3、（以左侧有序为例），如果nums[left] <= target <= nums[mid]不成立，那么target只可能存在于右侧。有意思的来了，我们发现对于右侧的元素再进行对半分之后，产生的左右侧两个数组也满足至少有一个有序这个条件，于是又可以对右侧的这两个数组进行1-3的步骤。
