Suppose a sorted array 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).You are given a target value to search. If found in the array return its index, otherwise return -1.You may assume no duplicate exists in the array.

 

 

public class Solution {    public int search(int[] nums, int target) {        if(nums==null || nums.length==0){            return -1;        }        int low=0;        int high=nums.length-1;                while(low<=high){            int mid=low+(high-low)/2;            if(target
     
      means,target cannot be in [low,mid] since this side is sorted                        low=mid+1;                    }                    else{                        high=mid-1;                    }                }            }            else if(target>nums[mid]){                                if(nums[mid]> nums[low]){
   //left side is sorted                    low=mid+1;                }                else{                    if(target>nums[high]){
   //target>nums[mid] && target>nums[high]==>means,target cannot be in [mid, high] since this side is sorted                        high=mid-1;                    }                    else{                        low=mid+1;                    }                }            }            else{                return mid;            }        }        return -1;    }}