# 33. 搜索旋转排序数组

<https://leetcode-cn.com/problems/search-in-rotated-sorted-array/>

两种解法本质上都是将数组限定在同一分支内，再用二分比较

## 解法一：二分

![](/files/-L_C0aUxp1oqnavdNJyv)

由于是翻转数组，且无重复，因此nums\[0]必然大于nums\[n-1]（为什么？写出来就知道），所有的数分成两支，每支内依然升序。问题是不知道**断点在哪**。

先取mid，看target与mid是否在同一支上，若在同一支（如左分支），在看是否在有序区间\[left, mid-1]，若在，就在左分支（\[left, mid-1])搜索，否则在右分支（\[mid+1, right])，以此类推。

算法：

1\) 每次检查`target == nums[mid]` ，若相等则找到

2\) 否则检查mid在左分支 (即 `nums[left] <= nums[mid]`)还是右分支。若在左分支，执行 步骤3), 若在右分支执行 步骤 4)

3\) 检查target是否在`[left, mid-1]` 范围内(即`nums[left] <= target < nums[mid]`), 若在，在左部分搜索 ，即 `right = mid-1`; 否则在右部分搜索，即`left = mid+1`;

4\) 检查target`[mid+1, right]` 范围内(即 `nums[mid] < target <= nums[right]`), 若在，在右部分搜索 ，即`left = mid+1`; 否则在左部分搜索，即 `right = mid-1`;

```python
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        n = len(nums)
        left, right = 0, n-1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] >= nums[left]:    #mid在左分支
            #elif nums[mid] >= nums[0]:    #其实严谨判断mid在左分支应该与0号比
                if nums[left] == target:    #若找到直接返回
                    return left
                elif nums[left] < target and target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:                            #mid在右分支
                if nums[right] == target:    #若找到直接返回
                    return right
                elif nums[mid] < target and target < nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
        return -1  #找不到
```

## 解法二：二分（用辅助tmp）

可以先取mid，看target与mid是否在同一支上，若在同一支，可以直接在该支上做二分查找。

若不在同一支，例如tar在左，mid在右，则下界往左收缩，然而不能直接比较tar和mi&#x64;**（因为不在同一支，直接比较无意义）**，这里处理断点用一个tmp辅助，用来与tar比较，若tar在左mid在右，显然无法直接二分，此时令tmp=正无穷，tar\<tmp，lo=mid+1。

反之若tar在右，mid在左，则上界往右收缩则令tmp=负无穷，易知hi=mid-1

```python
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        n = len(nums)
        lo, hi = 0, n-1
        tmp = 0
        while lo <= hi:  #二分查找
            mid = (lo + hi) // 2 
            if target > nums[0]:  #target在左分支
                if nums[mid] >= nums[0]:  #mid也在左分支
                    tmp = nums[mid]
                else:  #mid在右分支
                    tmp = float('inf')
            elif target == nums[0]:  #恰好等于左端点
                return 0
            elif target == nums[n-1]:  #恰好等于右端点
                return n-1
            elif target < nums[n-1]:  #target在右分支
                if nums[mid] < nums[0]:  #mid也在右分支
                    tmp = nums[mid]
                else:  #mid在左分支
                    tmp = -float('inf')
            #二分，用tmp而不是mid与tar比较
            if tmp < target:
                lo = mid + 1
            elif tmp > target:
                hi = mid - 1
            else:
                return mid
        return -1
```


---

# 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://cai-sen-se.gitbook.io/leetcode/1-200/33.-sou-suo-xuan-zhuan-pai-xu-shu-zu.md?ask=<question>
```

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.