Optimal Java AC Solution


  • 0
    O

    Single binary search inspired by https://leetcode.com/discuss/64618/ac-java-o-log-n-single-binary-search

    public int search(int[] nums, int target) {
        if (nums.length == 0) return -1;
        else if (nums.length == 1) return nums[0] == target ? 0 : -1;
        else if (nums[0] <= nums[nums.length - 1]) {
            int a = java.util.Arrays.binarySearch(nums, target);
            return Math.max(a, -1);
        }
        
        int lo = 0, hi = nums.length - 1;
        while (lo < hi) {
            if (hi - lo == 1)  return nums[lo] == target ? lo : nums[hi] == target ? hi : -1;
            
            int mid = (lo + hi) / 2;
            if (nums[mid] >= nums[0] && target < nums[0]) {
                lo = mid;
                continue;
            } else if (nums[mid] <= nums[0] && target >= nums[0]) {
                hi = mid;
                continue;
            }
            
            if (nums[mid] > target) {
                hi = mid;
            } else if (nums[mid] < target) {
                lo = mid;
            } else {
                return mid;
            }
        }
        
        return -1;
    }

Log in to reply
 

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