33.Search in Rotated Sorted Array
===
###### tags: `Medium`,`Array`,`Binary Search`
[33. Search in Rotated Sorted Array](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.
### 範例
**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
```
**Constraints**:
* 1 <= `nums.length` <= 5000
* -10^4^ <= `nums[i]` <= 10^4^
* All values of `nums` are **unique**.
* `nums` is an ascending array that is possibly rotated.
* -10^4^ <= `target` <= 10^4^
### 解答
#### Javascript
```javascript=
function search(nums, target) {
let min = 0;
let max = nums.length - 1;
while (max >= min) {
const mid = (max + min) >> 1;
if (nums[mid] === target) return mid;
if (nums[mid] >= nums[min]) {
if (target >= nums[min] && target < nums[mid]) {
max = mid - 1;
} else {
min = mid + 1;
}
} else {
if (target <= nums[max] && target > nums[mid]) {
min = mid + 1;
} else {
max = mid - 1;
}
}
}
return -1;
}
```
> [name=Marsgoat][time=Aug 8, 2023]
#### c#
```csharp=
public class Solution {
public int Search(int[] nums, int target) {
bool inLeft = target >= nums[0];
int left = 0;
int right = nums.Length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
if (inLeft && nums[mid] < nums[left]) {
right = mid - 1;
} else if (!inLeft && nums[mid] > nums[right]) {
left = mid + 1;
} else {
if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
}
return -1;
}
}
```
> [name=Jim][time=Aug 8, 2023]
### Reference
[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)