-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSolution33.cpp
More file actions
82 lines (80 loc) · 2.61 KB
/
Solution33.cpp
File metadata and controls
82 lines (80 loc) · 2.61 KB
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
//
// Solution33.cpp
// Algorithm
//
// Created by Pancf on 2020/10/14.
// Copyright © 2020 Pancf. All rights reserved.
//
#include "Solution33.hpp"
int Solution33::search(std::vector<int> &nums, int target)
{
// int lo = 0, hi = (int)nums.size() - 1;
// while (lo <= hi) {
// int mid = (lo + hi) / 2;
// // 此处必须是mid > hi，不能mid > lo，因为翻转前整个数组就是单调递增的，
// // mid > lo会把pivot = 0的情况也包括进去
// if (nums[mid] > nums[hi]) {
// // [lo, mid]为单调递增区间，[mid, hi]*一定*不是单调递增区间
// if (target == nums[mid]) {
// lo = mid;
// break;
// } else if (target > nums[mid] || target <= nums[hi]) {
// // target在（mid, hi]区间内（非单调递增）
// lo = mid + 1;
// } else {
// // target在[lo, mid)区间内
// hi = mid - 1;
// }
// } else {
// // [mid, hi]为单调递增区间，[lo, mid]*可能*是单调递增区间
// if (target == nums[mid]) {
// lo = mid;
// break;
// } else if (nums[mid] < target && target <= nums[hi]) {
// // target在(mid, hi]区间内
// lo = mid + 1;
// } else {
// // target在[lo, mid)区间内
// hi = mid - 1;
// }
// }
// }
// return target == nums[lo] ? lo : -1;
int lo = 0;
int hi = (int)nums.size() - 1;
// 寻找翻转点pivot
while (lo < hi) {
int mid = (lo + hi) / 2;
// 必须是mid > hi，不可以使用mid > lo
if (nums[hi] < nums[mid]) {
lo = mid + 1;
} else {
hi = mid;
}
}
int pivot = lo;
lo = 0;
hi = (int)nums.size() - 1;
// 第一次剪枝，最佳情况是将解空间缩小到1/2，最差情况是将解空间缩小一个值
if (0 < pivot && nums[lo] <= target && target <= nums[pivot - 1]) {
// target在[lo, pivot-1]中
hi = pivot - 1;
} else if (nums[pivot] <= target && target <= nums[hi]) {
// target 在[pivot, hi]中
lo = pivot;
} else {
return -1;
}
// 经过第一次剪枝，[lo, hi]已经是单调递增区间，进行常规的二分查找即可
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (nums[mid] < target) {
lo = mid + 1;
} else if (nums[mid] > target) {
hi = mid - 1;
} else {
return mid;
}
}
return -1;
}