###### tags: `LeetCode` `Binary Search` `Medium`
# LeetCode #33 [Search in Rotated Sorted Array](https://leetcode.com/problems/search-in-rotated-sorted-array/)
### (Medium)

整數數組 nums 按升序排列，數組中的值 互不相同 。

在傳遞給函數之前，nums 在預先未知的某個下標 k（0 <= k < nums.length）上進行了 旋轉，使數組變為 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下標 從 0 開始 計數）。例如， [0,1,2,4,5,6,7] 在下標 3 處經旋轉後可能變為 [4,5,6,7,0,1,2] 。

給你 旋轉後 的數組 nums 和一個整數 target ，如果 nums 中存在這個目標值 target ，則返回它的下標，否則返回 -1 。

---
因為這題要比較左右的值, 因此不能用左閉右開, 要使用左閉右閉。

首先比較中間的值與左邊的值, 若中值大於左值, 則代表左邊部分是正常的, 此時若目標值在左值範圍中則將右值改為中值, 其餘情況則將左值改為中值+1。

而若中值小於左值, 則代表中值-右值部分為正常遞增, 此時先檢查若目標值介於其中, 則將左值改為中值, 其餘情況則將右值改為中值-1。

---

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if(!nums.size())return -1;
        int l=0, r=nums.size()-1;
        while(l<r){
            int m = l+(r-l)/2;
            if(nums[m]==target)return m;
            if(nums[l]<=nums[m]){
                if(target>=nums[l]&&target<=nums[m])r=m;
                else l=m+1;
            }
            else{
                if(target>=nums[m]&&target<=nums[r])l=m;
                else r=m-1;
            }
        }
        if(target==nums[l])return l;
        return -1;
    }
};