13ms Commented Java Solution


  • 0
    A
    public class Solution {
        public static int search(int[] nums, int target) {
            int hi = nums.length - 1;
            int lo = 0;
            while (lo <= hi) {
                int mid = (lo + hi) / 2;
                // If lo .. mid is sorted.
                if (nums[mid] >= nums[lo]) {
                    if (target == nums[mid]) {
                        return mid;
                    }
                    if (target < nums[lo] || target > nums[mid]) {
                        // The target lies in the right side.
                        lo = mid + 1;
                    } else {
                        // target > nums[lo] and < nums[mid]
                        hi = mid - 1;
                    }
                } else {
                    if (target == nums[mid]) {
                        return mid;
                    }
    
                    if (target > nums[mid] && target < nums[lo]) {
                        lo = mid + 1;
                    } else {
                        hi = mid - 1;
                    }
                }
            }
            return -1;
        }
    }
    

    The intuition is this: If nums[lo] <= nums[mid], then [lo, mid] is sorted, and the pivot is from [mid, hi]. Given this information, we can infer where target should be for each case.


Log in to reply
 

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