Java 10 lines log(n) solution treating rotated array as if it is sorted


  • 1
    Y

    The inspiration comes from another post

    The idea is to adjust the elements of the array and target by adding Integer.MAX_VALUE to values that are less than nums[0]

    For example, 4 5 6 7 0 1 2 can be adjusted to 4 5 6 7 MAX+0 MAX+1 MAX+2
    If we want to search 5 we simply search 5 in the adjusted array.
    If we want to search 1 we search MAX+1 in the adjusted array.
    The adjustment should happen on the fly, so it should only cost O(log(n)) overall.

    Here is one accepted solution:

        public int search(int[] nums, int target) {
            int l = 0, h = nums.length - 1;
            long t = adjust(nums[0], target);
            while (l <= h) {
                int mid = (l + h) >>> 1;
                long m = adjust(nums[0], nums[mid]);
                if (t == m) return mid;
                else if (t < m) h = mid - 1;
                else l = mid + 1;
            }   
            return -1; 
        }   
    
        static long adjust(int n0, int n) {
            return n < n0 ? n + (long) Integer.MAX_VALUE : n;
        }
    

    But what if the array is long[]?
    Then we can also apply the same idea without adding MAX
    All we need to do is to treat the numbers that are less than nums[0] as if they are greater.

    Here is another solution:

        public int search(int[] nums, int target) {
            int l = 0, h = nums.length - 1, n0 = nums[0];
            while (l <= h) {
                int mid = (l + h) >>> 1, m = nums[mid];
                if (target == m) return mid;
                else if (m < n0 == target < n0 && target < m || target >= n0 && m < n0)
                    h = mid - 1;
                else 
                    l = mid + 1;
            }   
            return -1; 
        }
    

Log in to reply
 

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