Simple (Not Optimal) Java AC Solution


  • 0
    O
    public int search(int[] nums, int target) {
        int pivot = findPivot(nums);
        int pos = java.util.Arrays.binarySearch(nums, 0, pivot, target);
        if (pos < 0) {
            pos = java.util.Arrays.binarySearch(nums, pivot, nums.length, target);
            if (pos < 0) {
                pos = -1;
            }
        }
        return pos;
    }
    
    private int findPivot(int[] nums) {
        if (nums.length <= 1 || nums[0] <= nums[nums.length - 1]) return 0;
        
        int pivot = 0, lo = 0, hi = nums.length - 1, mid;
        while (lo < hi) {
            if (hi - lo == 1) {
                pivot = nums[lo] < nums[hi] ? lo : hi;
                break;
            }
            
            mid = (lo + hi) / 2;
            if (nums[lo] > nums[mid]) {
                hi = mid;
            } else {
                lo = mid;
            }
        }
        
        if (lo == hi) pivot = lo;
        return pivot;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.