# 33. Search in Rotated Sorted Array

### Leetcode

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

### 題目

There is an integer array `nums` sorted in ascending order (with **distinct** values).

Prior to being passed to your function, `nums` is **possibly rotated** at an unknown pivot index `k` (`1 <= k < nums.length`) such that the resulting array is `[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]` (**0-indexed**). For example, `[0,1,2,4,5,6,7]` might be rotated at pivot index `3` and become `[4,5,6,7,0,1,2]`.

Given the array `nums` **after** the possible rotation and an integer `target`, return *the index of* `target` *if it is in* `nums`*, or* `-1` *if it is not in* `nums`.

You must write an algorithm with `O(log n)` runtime complexity.

&#x20;

**Example 1:**

```
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
```

**Example 2:**

```
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
```

**Example 3:**

```
Input: nums = [1], target = 0
Output: -1
```

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一**

先找出整個矩陣最大值的 index (rotateIndex)，再看 target 應該是要在 rotateIndex 的左邊或右邊開始找

```
var search = function(nums, target) {
    const getRotateIndex = () => {
        let rotateIndex = 0;
        let low = 0;
        let high = nums.length - 1;
        
        while(low < high) {
            const mid = Math.ceil((low+high) / 2);
            if(nums[mid] > nums[rotateIndex]) {
                rotateIndex = mid;
                low = mid;
            } else {
                high = mid - 1;
            }
        }
        return rotateIndex;
    }
    
    // 找出矩陣最大值的 index
    const rotateIndex = getRotateIndex();
    // 目標值是否該從左邊開始找
    const isSearchLeftPart = target >= nums[0];
    let [low, high] = isSearchLeftPart ? [0, rotateIndex] : [rotateIndex + 1, nums.length - 1]
    // console.log(rotateIndex, low, high)
    
    while(low < high) {
        const mid = Math.floor((low+high) / 2);
        if(target === nums[mid]) return mid;
        if(target < nums[mid]) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    // 如果找到最後還是不等於 target 的話，等於不存在 return -1
    return nums[low] !== target ? -1 : low;
};
```

Runtime: 109 ms, faster than 14.09% of JavaScript online submissions for Search in Rotated Sorted Array.

Memory Usage: 39.6 MB, less than 83.42% of JavaScript online submissions for Search in Rotated Sorted Array.

* **方法二**

每次 binary search 時都根據 mid 跟 target 及 nums\[0] 之間的大小關係，決定怎麼設定下次搜尋的上下限

```
var search = function(nums, target) {
    let low = 0;
    let high = nums.length - 1;
    
    if(target === nums[0]) return 0;
    
    while(low < high) {
        const mid = Math.floor((low+high) / 2);
        if(target === nums[mid]) return mid;
        // 代表 mid 的位置是在 nums 矩陣的左邊
        if(nums[mid] >= nums[0]) {
            // target 在 nums 矩陣的左邊
            if(target > nums[0]) {
                if(target > nums[mid]) low = mid + 1;
                else high = mid;
            } else low = mid + 1;
        } else {
            // target 在 nums 矩陣的左邊，但是 mid 在 nums 矩陣右邊，所以 high 設成 mid
            if(target > nums[0]) high = mid;
            else {
                // target 在 nums 矩陣的右邊，mid 在 nums 矩陣右邊，且 target > nums[mid]
                // 所以往右邊找 low 設成 mid + 1
                if(target > nums[mid]) low = mid + 1;
                else high = mid;
            }
        }
    }
    return nums[low] !== target ? -1 : low;
};
```

Runtime: 76 ms, faster than 71.83% of JavaScript online submissions for Search in Rotated Sorted Array.

Memory Usage: 40.1 MB, less than 37.65% of JavaScript online submissions for Search in Rotated Sorted Array.

### 測資

```
let nums = [4,5,6,7,0,1,2], target = 0; // 4
// nums = [4,5,6,7,0,1,2], target = 3; // -1
// nums = [1], target = 0; // -1
// nums = [1], target = 1; // 0
// nums = [1, 3], target = 3; // 1

console.log(search(nums, target))
```
