> For the complete documentation index, see [llms.txt](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/33.search-in-rotated-sorted-array.md).
# 0033. 搜索旋转排序数组
### 题目地址(33. 搜索旋转排序数组)
### 题目描述
```
给你一个升序排列的整数数组 nums ，和一个整数 target 。
假设按照升序排序的数组在预先未知的某个点上进行了旋转。（例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] ）。
请你在数组中搜索 target ，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
示例 3：
输入：nums = [1], target = 0
输出：-1
提示：
1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
nums 中的每个值都 独一无二
nums 肯定会在某个点上旋转
-10^4 <= target <= 10^4
```
### 前置知识
* 数组
* 二分法
### 公司
* 阿里
* 腾讯
* 百度
* 字节
### 思路
这是一个我在网上看到的前端头条技术终面的一个算法题。
题目要求时间复杂度为 logn，因此基本就是二分法了。 这道题目不是直接的有序数组，不然就是 easy 了。
首先要知道，我们随便选择一个点，将数组分为前后两部分，其中一部分一定是有序的。
具体步骤：
* 我们可以先找出 mid，然后根据 mid 来判断，mid 是在有序的部分还是无序的部分
假如 mid 小于 start，则 mid 一定在右边有序部分。 假如 mid 大于等于 start， 则 mid 一定在左边有序部分。
> 注意等号的考虑
* 然后我们继续判断 target 在哪一部分， 我们就可以舍弃另一部分了
我们只需要比较 target 和有序部分的边界关系就行了。 比如 mid 在右侧有序部分，即\[mid, end] 那么我们只需要判断 target >= mid && target <= end 就能知道 target 在右侧有序部分，我们就 可以舍弃左边部分了(start = mid + 1)， 反之亦然。
我们以(\[6,7,8,1,2,3,4,5], 4)为例讲解一下：
### 关键点解析
* [二分法](/leetcode-solution/91/binary-search.md)
* 找出有序区间，然后根据 target 是否在有序区间舍弃一半元素
### 代码
* 语言支持: Javascript，Python3
```js
/*
* @lc app=leetcode id=33 lang=javascript
*
* [33] Search in Rotated Sorted Array
*/
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var search = function (nums, target) {
// 时间复杂度：O(logn)
// 空间复杂度：O(1)
// [6,7,8,1,2,3,4,5]
let start = 0;
let end = nums.length - 1;
while (start <= end) {
const mid = start + ((end - start) >> 1);
if (nums[mid] === target) return mid;
// [start, mid]有序
// ️⚠️注意这里的等号
if (nums[mid] >= nums[start]) {
//target 在 [start, mid] 之间
// 其实target不可能等于nums[mid]， 但是为了对称，我还是加上了等号
if (target >= nums[start] && target <= nums[mid]) {
end = mid - 1;
} else {
//target 不在 [start, mid] 之间
start = mid + 1;
}
} else {
// [mid, end]有序
// target 在 [mid, end] 之间
if (target >= nums[mid] && target <= nums[end]) {
start = mid + 1;
} else {
// target 不在 [mid, end] 之间
end = mid - 1;
}
}
}
return -1;
};
```
Python3 Code:
```python
class Solution:
def search(self, nums: List[int], target: int) -> int:
"""用二分法，先判断左右两边哪一边是有序的，再判断是否在有序的列表之内"""
if len(nums) <= 0:
return -1
left = 0
right = len(nums) - 1
while left < right:
mid = (right - left) // 2 + left
if nums[mid] == target:
return mid
# 如果中间的值大于最左边的值，说明左边有序
if nums[mid] > nums[left]:
if nums[left] <= target <= nums[mid]:
right = mid
else:
# 这里 +1，因为上面是 <= 符号
left = mid + 1
# 否则右边有序
else:
# 注意：这里必须是 mid+1，因为根据我们的比较方式，mid属于左边的序列
if nums[mid+1] <= target <= nums[right]:
left = mid + 1
else:
right = mid
return left if nums[left] == target else -1
```
**复杂度分析**
* 时间复杂度：$O(logN)$
* 空间复杂度：$O(1)$
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 