33. Search in Rotated Sorted Array

Posted on | Edited on | Views:

LeetCode

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
class Solution {
    public int search(int[] nums, int target) {
        if(nums.length==0) return -1;
        
        int lo=0,hi=nums.length-1;
        while(lo<hi){
            int mid=(lo+hi)/2;
            if(nums[mid]>nums[hi]) lo=mid+1;
            else hi=mid;
        }
        int pivot=lo;
        if(target>nums[nums.length-1]) return binary_search(0,pivot-1,nums, target);
        return binary_search(pivot,nums.length-1,nums,target);
    }
    public int binary_search(int lo,int hi,int[] nums, int target){
        int mid;
        while(lo<=hi){
            mid=(lo+hi)/2;
            if(nums[mid]==target) return mid;
            else if(nums[mid]<target) lo=mid+1;
            else hi=mid-1;
        }
        return -1;
    }
}
0%