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)