33. 搜索旋转排序数组
程序员文章站
2022-07-08 16:02:45
...
1.题目
2.解法
class Solution{
public int search(int[] nums, int target) {
if (nums.length == 0 || nums == null) {
return -1;
}
int start = 0;
int end = nums.length - 1;
while (start <= end) {
// 1234
// 如果end = length, 那么mid = 3; 如果length - 1, 就为2
int mid = (start + end) / 2;
if (nums[mid] == target) {
return mid;
}
// 判断前部分是否有序
if (nums[start] <= nums[mid]) {
if (nums[start] <= target && target < nums[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
} else {
if (nums[mid] < target && target <= nums[end]) {
start = mid + 1;
} else {
end = mid - 1;
}
}
}
return -1;
}
}
时间复杂度 O(logn)(带数值进去算就可知道,算出来的值向上向下取值都可以,如果end=length,会比end=length-1多执行1次),空间复杂度O(1)
3.思考
上一篇: 堆和堆排序