# 33 Search in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

example:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Concept 用binary search搜尋。 每次取最中間的數字，和最左、最右比較，看左邊是上升順序還是右邊是上升順序，看target有沒有在上升順序的那一邊，若有則把左右index設為左邊array的邊界，否則設為右邊array的邊界。

Pseudocode

while(left <= right){
    middle = (left+right)/2;

    if(middle == target)    return middle
    if(left side is in ascending order)
        if target is in left side
            set right to mid
        else
            set left to mid+1

    if(right side is in ascending order)
        if target is in right side
            set left to mid +1
        else
            set right to mid
}

return -1

Code

class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length-1;

        while(l <= r){
            int m = l + (r-l)/2;

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

            if(nums[m] >= nums[l]){
                if(target <= nums[m] && target >= nums[l]){
                    r = m;
                }else{
                    l = m + 1;
                }
            }

            if(nums[m] <= nums[r]){
                if(target > nums[m] && target <= nums[r]){
                    l = m+1;
                }else{
                    r = m;
                }
            }
        }

        return -1;
    }
}