- 要求
O(log n)
时间复杂度,数组有序,因此应当使用二分搜索
- 对于旋转过的数组,中间值的左右侧,必然有一侧是升序排列的
$$$@@@ // $$$ 和 @@@ 为旋转后有序的两部分
$$$ 中的任何元素,其左侧都位于 $$$ 中,必然有序
@@@ 中的任何元素,其右侧都位于 @@@ 中,必然有序
class Solution {
public:
int search(vector<int>& nums, int target) {
if (empty(nums)) {
return -1;
}
int l = 0;
int r = size(nums);
while (l != r) {
int m = l + (r - l) / 2;
if (target == nums[m]) {
return m;
}
if (nums[m] >= nums[l]) { // 左侧升序
if (target < nums[m] && target >= nums[l]) { // 位于左侧
r = m;
} else {
l = m + 1;
}
} else { // 左侧不为升序则右侧一定为升序
if (target > nums[m] && target <= nums[r - 1]) { // 位于右侧
l = m + 1;
} else {
r = m;
}
}
}
return -1;
}
};