LeetCode 33. 搜索旋转排序数组
题目描述
思路分析
二分查找
如果中间的数小于最右边的数，则右半部分是有序的。
如果中间的数大于最右边的数，则左半部分是有序的。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func search(nums []int, target int) int {
left, right := 0, len(nums)-1
for left <= right {
mid := left + (right-left)/2
if nums[mid] == target {
return mid
}
if nums[mid] > nums[right] {
// 左半部分有序
if target >= nums[left] && target < nums[mid] {
right = mid - 1
} else {
left = mid + 1
}
} else if nums[mid] < nums[right] {
// 右半部分有序
if target > nums[mid] && target <= nums[right] {
left = mid + 1
} else {
right = mid - 1
}
} else {
right--
}
}
return -1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[mid] > nums[right]) {
if (target >= nums[left] && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else if ((nums[mid] < nums[right])) {
if (target > nums[mid] && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
} else {
right--;
}
}
return -1;
}
}
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！