思路：二分法
-
数组旋转后即分成左右两部分，都是各自有序的 ！
-
二分法，分为两种情况：
如果nums[mid]在左边，
①再判断target是否也在左边，如果是则将 right 左移，
②否则即target在右边，则将left 右移；如果
nums[mid]在右边，
①再判断target是否也在右边，如果是则将 left 右移，
②否则即target在左边，则将right 左移；
Java实现：
class Solution {
public int search(int[] nums, int target) {
if(nums.length==0){
return -1;
}
if(nums.length==1){
return nums[0]==target? 0:-1;
}
int n=nums.length;
int i=0;
int j=n-1;
while(i<=j){
int mid=i+(j-i)/2;
if(nums[mid]==target){
return mid;
// 如果mid在左边, 注意nums[mid]可能等于nums[0]
}else if(nums[0]<=nums[mid]){
// target也在左边
if(nums[0]<=target && target<nums[mid]){
j=mid-1;
}else{
i=mid+1;
}
// 如果mid在右边
}else if(nums[mid]<nums[0]){
// target也在右边
if(nums[mid]<target && target<=nums[n-1]){
i=mid+1;
}else{
j=mid-1;
}
}
}
return -1;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/89161.html
