问题背景
整数数组
n
u
m
s
nums
nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，
n
u
m
s
nums
nums 在预先未知的某个下标
k
(
0
≤
k
<
n
u
m
s
.
l
e
n
g
t
h
)
k(0 \le k \lt nums.length)
k(0≤k<nums.length) 上进行了 旋转，使数组变为
[
n
u
m
s
[
k
]
,
n
u
m
s
[
k
+
1
]
,
.
.
.
,
n
u
m
s
[
n
−
1
]
,
n
u
m
s
[
0
]
,
n
u
m
s
[
1
]
,
.
.
.
,
n
u
m
s
[
k
−
1
]
]
[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]
[nums[k],nums[k+1],...,nums[n−1],nums[0],nums[1],...,nums[k−1]]（下标 从
0
0
0 开始 计数）。例如，
[
0
,
1
,
2
,
4
,
5
,
6
,
7
]
[0,1,2,4,5,6,7]
[0,1,2,4,5,6,7] 在下标
3
3
3 处经旋转后可能变为
[
4
,
5
,
6
,
7
,
0
,
1
,
2
]
[4,5,6,7,0,1,2]
[4,5,6,7,0,1,2]。
给你 旋转后 的数组
n
u
m
s
nums
nums 和一个整数
t
a
r
g
e
t
target
target，如果
n
u
m
s
nums
nums 中存在这个目标值
t
a
r
g
e
t
target
target，则返回它的下标，否则返回
−
1
-1
−1。
你必须设计一个时间复杂度为
O
(
l
o
g
n
)
O(log n)
O(logn) 的算法解决此问题。
数据约束
- 1 ≤ n u m s . l e n g t h ≤ 5000 1 \le nums.length \le 5000 1≤nums.length≤5000
- − 1 0 4 ≤ n u m s [ i ] ≤ 1 0 4 -10 ^ 4 \le nums[i] \le 10 ^ 4 −104≤nums[i]≤104
- n u m s nums nums 中的每个值都 独一无二
- 题目数据保证 n u m s nums nums 在预先未知的某个下标上进行了旋转
- − 1 0 4 ≤ t a r g e t ≤ 1 0 4 -10 ^ 4 \le target \le 10 ^ 4 −104≤target≤104
解题过程
可以用两次二分来解决，找到数组中的最小值，然后比较待查找目标和数组中最后一个元素的大小，到对应的范围上再来一次 二分查找 获得结果。
这题可以通过精确划分类别，用一次二分就解决。但是这种做法没有任何时空效率上的提升，反而会让代码可读性变得非常差，就不写了。
具体实现
class Solution {
public int search(int[] nums, int target) {
int n = nums.length;
int minIndex = findMin(nums);
if(target > nums[n - 1]) {
return binarySearch(nums, target, 0, minIndex);
}
return binarySearch(nums, target, minIndex, n);
}
// Leetcode 33.搜索旋转排序数组
private int findMin(int[] nums) {
int n = nums.length;
int left = 0, right = n - 1;
while(left < right) {
int mid = left + ((right - left) >>> 1);
if(nums[mid] > nums[n - 1]) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
// Leetcode 35.搜索插入位置
private int binarySearch(int[] nums, int target, int left, int right) {
while(left < right) {
int mid = left + ((right - left) >>> 1);
if(nums[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return nums[left] == target ? left : -1;
}
}
