# 33 - Search in Rotated Sorted Array

解法一 - Binary Search

這題的 array 因為被轉過，所以變成只有部分有排好序，但如果我們把 array 切成兩半，一定有一邊是已經排好序的，所以我們透過更新 begin 跟 end 就可以一直縮小搜索的範圍：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int begin = 0, end = nums.size()-1;
        if(end < 0) return -1;

        while(begin+1 < end) {
            int mid = begin + (end-begin)/2;

            if(nums[mid] == target) return mid;

            if(nums[mid] > nums[begin]) {
                if(nums[begin] <= target && target <= nums[mid]) end = mid;
                else begin = mid;
            }
            if(nums[mid] < nums[begin]) {
                if(nums[mid] <= target && target <= nums[end]) begin = mid;
                else end = mid;
            }
        }

        if(nums[begin] == target) return begin;
        else if(nums[end] == target) return end;
        else return -1;
    }
};