# 33. Search in Rotated Sorted Array

## Problem

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., `0 1 2 4 5 6 7` might become `4 5 6 7 0 1 2`).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

**Related Topics:**

`Array` `Binary Search`

## Analysis

方法一：先找出最小值所在的下标，确定目标在哪一边，然后进行二分查找。

方法二：当 `target < nums[mid]` 时，存在三种情况。

* 两则都在分割线（最小值与最大值之间）的左边：为升序，`target` 在 `nums[mid]` 左边，所以 `nums[mid]` 右边的元素舍弃，即 `end = mid - 1`。
* 两则都在分割线的右边：为升序，同上，`end = mid - 1`。
* 由于分割线左边元素大于右边，所以 `target` 在右边，`nums[mid]` 在左边：舍弃 `nums[mid]` 左边元素，即 `start = mid + 1`。

同理，`target > nums[mid]` 时，也有三种情况，处理方法类似。

## Code

**找最小值：**

```kotlin
class Solution {

    fun search(nums: IntArray, target: Int): Int {

        if (nums.isEmpty()) return -1

        val minIndex = findMin(nums)
        var start: Int
        var end: Int
        var mid: Int

        when {
            target > nums[nums.lastIndex] -> {
                start = 0
                end = minIndex - 1
            }
            else -> {
                start = minIndex
                end = nums.lastIndex
            }
        }

        while (start <= end) {
            mid = (start + end) / 2
            when {
                target == nums[mid] -> return mid
                target < nums[mid] -> end = mid - 1
                target > nums[mid] -> start = mid + 1
            }
        }

        return -1
    }

    private fun findMin(nums: IntArray): Int {

        var start = 0
        var end = nums.lastIndex
        var mid: Int

        while (start < end) {
            mid = (start + end) / 2
            when {
                nums[mid] > nums[end] -> start = mid + 1
                else -> end = mid
            }
        }

        return start
    }
}
```

**所有情况判断：**

```kotlin
class Solution {

    fun search(nums: IntArray, target: Int): Int {

        var start = 0
        var end = nums.lastIndex
        var mid: Int

        while (start <= end) {

            mid = (start + end) / 2

            when {
                target > nums[end] && nums[mid] <= nums[end] -> end = mid - 1
                target <= nums[end] && nums[mid] > nums[end] -> start = mid + 1
                else -> {
                    when {
                        target < nums[mid] -> end = mid - 1
                        target > nums[mid] -> start = 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://pachirisu.gitbook.io/leetcode-algorithms/33.-search-in-rotated-sorted-array.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.