51 lines
1.7 KiB
C++
51 lines
1.7 KiB
C++
#include "s0033_search_in_rotated_sorted_array.hpp"
|
|
|
|
// 看到 O(logN) 的搜索算法，立马想到二分法
|
|
// 可是二分法要求数组已排序，旋转数组又如何用二分法呢？
|
|
// 思路很简单，对数组二分，有一半一定是有序的，另一半可能有序可能无序
|
|
// 对有序的一半进行二分搜索，无序的部分再次进行二分，如此迭代
|
|
|
|
int S0033::search(vector<int>& nums, int target) {
|
|
int size = nums.size();
|
|
int left{0};
|
|
int right = size - 1;
|
|
int mid = static_cast<int>(floor((left + right) / 2));
|
|
while (left <= right) {
|
|
mid = static_cast<int>(floor((left + right) / 2));
|
|
// 数组有序
|
|
if (nums[left] <= nums[right]) {
|
|
// 越界
|
|
if (target > nums[right] || target < nums[left]) {
|
|
return -1;
|
|
}
|
|
// 二分查找
|
|
if (nums[mid] == target) {
|
|
return mid;
|
|
} else if (nums[mid] < target) {
|
|
left = mid + 1;
|
|
} else {
|
|
right = mid - 1;
|
|
}
|
|
} else { // 数组无序
|
|
// 左半部分有序
|
|
if (nums[mid] >= nums[left]) {
|
|
// 如果 target 在左半部分，则更新 right 然后继续迭代
|
|
if (target <= nums[mid] && target >= nums[left]) {
|
|
right = mid;
|
|
} else { // target 位于右半部分或者越界
|
|
// 我们不在这里处理越界，因为越界的情况包含在了这个 else
|
|
// 语句里，继续迭代下去会出循环，然后返回 -1
|
|
left = mid + 1;
|
|
}
|
|
} else { // 右半部分有序
|
|
if (target >= nums[mid] && target <= nums[right]) {
|
|
left = mid;
|
|
} else {
|
|
right = mid - 1;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
return -1;
|
|
}
|