文章目录
1、题目描述2、解题思路3、解题代码
1、题目描述
2、解题思路
输入的数组是一个升序排序数组的旋转，可以看成如下图所示的状态：
如果对于每一次调整区间范围，都有以下两种情况：
1、mid 在左侧部分
此时，参照对象就是 nums[0]，如果目标值大于等于它，且目标值小于 nums[mid]，则 r = mid - 1，否则 l = mid + 1。
2、mid 在右侧部分
此时，参照对象是 nums[n-1] ，如果目标值小于等于它，且目标值大于 nums[mid]，则 l = mid + 1，否则 r = mid + 1。
3、解题代码
class Solution {
public int search(int[] nums
, int target
) {
int n
= nums
.length
;
if (n
== 0) {
return -1;
}
if (n
== 1) {
return nums
[0] == target
? 0 : -1;
}
int l
= 0, r
= n
- 1;
while (l
<= r
) {
int mid
= l
+ (r
- l
) / 2;
if (nums
[mid
] == target
) {
return mid
;
}
if (nums
[0] <= nums
[mid
]) {
if (nums
[0] <= target
&& target
< nums
[mid
]) {
r
= mid
- 1;
} else {
l
= mid
+ 1;
}
} else {
if (nums
[mid
] < target
&& target
<= nums
[n
- 1]) {
l
= mid
+ 1;
} else {
r
= mid
- 1;
}
}
}
return -1;
}
}
