方法一: 先找到旋转点, 然后根据目标值重新确定二分查找区域.
时间复杂度: 用到两次二分查找, 每次二分查找粗略的认为是 O(logn), 那么时间复杂度为 2 * O(logn);
空间复杂度: O(1).
- int search(vector<int>& nums, int target) {
- if (!nums.size()) return -1;
- int low = 0, high = nums.size() - 1, mid;
- int rotate = 0; // 旋转点
- // 第一步先找到旋转点
- if (nums[low] <= nums[high]) rotate = 0; // 无旋转
- else
- {
- while (low <high)
- {
- mid = low + ((high - low)>> 1);
- if (nums[mid]> nums[mid + 1]) break;
- if (nums[mid]>= nums[low]) low = mid;
- else high = mid;
- }
- rotate = mid + 1;
- }
- // 重新规划二分查找区域
- if (!rotate)
- {
- low = 0;
- high = nums.size() - 1;
- }
- else
- {
- if (nums[0] == target) return 0;
- else if (nums[0]> target)
- {
- low = rotate;
- high = nums.size() - 1;
- }
- else
- {
- low = 0;
- high = rotate - 1;
- }
- }
- // 二分查找
- while (low <= high)
- {
- mid = low + ((high - low)>> 2);
- if (nums[mid] == target) return mid;
- else if (nums[mid]> target) high = mid - 1;
- else low = mid + 1;
- }
- return -1;
- }
方法二: 根据中间点和其他条件来调整上下边界. 其实一开始就想的这个办法, 但是写的过程中发现很混乱, 所以就写了上一种比较清晰的方法. 这个方法的关键是确定哪半边是有序的, 在这个前提下分情况讨论会很清晰.
时间复杂度: O(logn), 空间复杂度: O(1).
- int search(vector<int>& nums, int target) {
- if (!nums.size()) return -1; // 数组为空
- int low = 0, high = nums.size() - 1, mid;
- if (nums[low] <= nums[high]) // 数组无旋转点, 即升序排列
- {
- while (low <= high)
- {
- mid = low + ((high - low)>> 1);
- if (nums[mid] == target) return mid;
- else if (nums[mid]> target) high = mid - 1;
- else low = mid + 1;
- }
- return -1;
- }
- else // 数组有旋转点
- {
- while (low <= high)
- {
- mid = low + ((high - low)>> 1);
- if (nums[mid] == target) return mid;
- if (nums[mid]> nums[low]) // 左半边有序
- {
- if (nums[low] <target && nums[mid]> target) high = mid - 1;
- else if (nums[low] == target) return low;
- else low = mid + 1;
- }
- else // 右半边有序
- {
- if (nums[high]> target && nums[mid] < target) low = mid + 1;
- else if (nums[high] == target) return high;
- else high = mid - 1;
- }
- }
- return -1;
- }
- }
总结: 1) 分析时把握问题的特征, 不要没有头绪的想, 不然就是猜了;
2)O(logn) 复杂度是非常优秀的时间复杂度.
来源: https://www.cnblogs.com/zpchya/p/10727120.html