【面试经典 150 | 二分查找】搜索旋转排序数组

文章目录

写在前面
Tag
题目来源
解题思路
- 方法一：二分查找
写在最后

写在前面

本专栏专注于分析与讲解【面试经典150】算法，两到三天更新一篇文章，欢迎催更……

专栏内容以分析题目为主，并附带一些对于本题涉及到的数据结构等内容进行回顾与总结，文章结构大致如下，部分内容会有增删：

Tag：介绍本题牵涉到的知识点、数据结构；
题目来源：贴上题目的链接，方便大家查找题目并完成练习；
题目解读：复述题目（确保自己真的理解题目意思），并强调一些题目重点信息；
解题思路：介绍一些解题思路，每种解题思路包括思路讲解、实现代码以及复杂度分析；
知识回忆：针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

Tag

【数组】【二分查找】

题目来源

33. 搜索旋转排序数组

解题思路

方法一：二分查找

本题有两处提示，提示本题可以使用二分查找解题：

有序数组
设计一个时间复杂度为 $O (l o g n)$ 的算法解题

思路

通常使用二分查找解题，需要一个前提——数组是有序的，本题的数组虽然并不是完全有序，但却是部分有序的。对于这样的数组，我们依然可以使用二分查找完成搜索任务。

我们从数组中间将原数组分为两部分，这样两部分中总有一部分数组是有序的。我们优先在有序的部分中进行二分查找。根据查找的结果变动二分查找的左右范围：

如果 [l, mid - 1] 是有序的，且 target 的值在范围 [nums[l], nums[mid]) 内，则我们应该将搜索范围缩小值 [l, mid - 1]，否则在 [mid + 1, r] 中寻找。
如果 [mid, r] 是有序的，且 target 的值在范围 [nums[mid+1], nums[r]) 内，则我们应该将搜索范围缩小值 [mid, r]，否则在 [l, mid - 1] 中寻找。

代码

class Solution {
public:
	int search(vector<int>& nums, int target) {
		int n = (int)nums.size();
		int l = 0, r = n - 1;

        if(n == 1)
            return nums[0] == target? 0: -1;
		while (l <= r) {
			int mid = (l + r) / 2;
			if (nums[mid] == target)
				return mid;

			if (nums[0] <= nums[mid]) {
				if (nums[0] <= target && target < nums[mid])
					r = mid - 1;
				else
					l = mid + 1;
			}
			else {
				if (nums[mid] < target && target <= nums[n - 1])
					l = mid + 1;
				else
					r = mid - 1;
			}
		}
		return -1;
	}
};