(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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | public class Solution { //this is a more general binary search, it handles sorted array too public int search(int[] nums, int target) { int l=0,r=nums.length-1; if(nums.length==1&&nums[0]==target)return 0; while(l<=r){//so it can process situation of two numbers int mid=l+(r-l)/2; if(nums[mid]==target)return mid; //in a rotated array, there must be one half is sorted //we try to identify the sorted part out and start from dealng with it because it is easier if(nums[mid]<=nums[r]){ //sorted part is right array if(target>nums[mid]&&target<=nums[r]) l=mid+1;//we know mid is not the selection because otherwise it's returned else//it's not in right, then it is in left r=mid-1; }else{//then sorted part is in left if(target>=nums[l]&&target<nums[mid])//it is within sorted left array r=mid - 1; else//if not, it is in right part l = mid+1; } } return -1; } } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | public int search(int[] nums, int target) { return searchRec(nums,target,0,nums.length-1); } public int searchRec(int[] nums, int target,int left, int right) { if(nums.length==1&&nums[0]==target)return 0; if(left>=right){ if(nums[left]==target)return left; else return -1; } int mid=left+(right-left)/2; if(nums[mid]==target)return mid; //in a rotated array, there must be one half is sorted //we try to identify the sorted part out and start from dealng with it because it is easier if(nums[mid]<=nums[right]){ //sorted part is right array if(target>nums[mid]&&target<=nums[right]) return searchRec(nums,target,mid+1,right);//we know mid is not the selection because otherwise it's returned else//it's not in right, then it is in left return searchRec(nums,target,left,mid-1); }else{//then sorted part is in left if(target>=nums[left]&&target<nums[mid])//it is within sorted left array return searchRec(nums,target,left,mid - 1); else//if not, it is in right part return searchRec(nums,target,mid+1,right); } } |
