# 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 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/33.search-in-rotated-sorted-array.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.