# 33 Search in Rotated Sorted Array

Concept:

always do binary search on the side that is in increasing order

use 3 pointers: start, end, mid

Pseudocode:

while(start<=end)
    mid = (start + end)/2
    if nums[mid] == target
        return mid
    if(nums[mid] >= nums[start])
        if target is in the range between start and mid
            end = mid-1
        else
            start = mid+1
    if(nums[mid]<= nums[end])
        if target is in the range between mid and end
            start = mid+1
        else
            end = mid-1
return -1

Code:

public class Solution {
    public int search(int[] nums, int target) {

        int start = 0, end = nums.length-1, mid;
        while(start <= end){
            mid = (start+end)/2;
            System.out.println(mid);
            if(nums[mid]==target)
                return mid;
            if(nums[mid]>=nums[start]){
                if(target>=nums[start] && target<nums[mid])
                    end = mid-1;
                else
                    start = mid+1;
            }
            if(nums[mid]<=nums[end]){
                if(target>nums[mid] && target<=nums[end])
                    start = mid+1;
                else
                    end = mid-1;
            }
        }
        return -1;
    }
}