Leetcode --- Search in Rotated Sorted Array
===

## Binary Search

由題目可知，該陣列是由兩段排序好的數列組成的，而我們正在查找的目標是左邊排序還是右邊排序可以跟最左邊的數字比較，num[l]> num[i]表示右邊排序，反之左邊排序

因此BS在找的過程中，如果target在對應的排序範圍內，則可以用一般的BS找，反之應該調整l跟r的位置

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l= 0, r= nums.size()-1;

        while(l<= r)
        {
            int mid= l+ (r-l)/2;
            if(target == nums[mid]) return mid;
            else if(nums[l] <= nums[mid]) //l ~ mid sorted
            {
                if(target< nums[mid] && target >= nums[l]) r= mid-1;
                else l = mid+ 1;
            }
            else
            {
                if(target> nums[mid] && target <= nums[r]) l= mid+1;
                else r= mid-1;
            }
        }

        return -1;
    
    }
};

###### tags: `Leetcode`