Clever idea making it simple


  • 127

    This very nice idea is from rantos22's solution who sadly only commented "You are not expected to understand that :)", which I guess is the reason it's now it's hidden among the most downvoted solutions. I present an explanation and a more usual implementation.


    Explanation

    Let's say nums looks like this: [12, 13, 14, 15, 16, 17, 18, 19, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

    Because it's not fully sorted, we can't do normal binary search. But here comes the trick:

    • If target is let's say 14, then we adjust nums to this, where "inf" means infinity:
      [12, 13, 14, 15, 16, 17, 18, 19, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]

    • If target is let's say 7, then we adjust nums to this:
      [-inf, -inf, -inf, -inf, -inf, -inf, -inf, -inf, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

    And then we can simply do ordinary binary search.

    Of course we don't actually adjust the whole array but instead adjust only on the fly only the elements we look at. And the adjustment is done by comparing both the target and the actual element against nums[0].


    Code

    If nums[mid] and target are "on the same side" of nums[0], we just take nums[mid]. Otherwise we use -infinity or +infinity as needed.

    int search(vector<int>& nums, int target) {
        int lo = 0, hi = nums.size();
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            
            double num = (nums[mid] < nums[0]) == (target < nums[0])
                       ? nums[mid]
                       : target < nums[0] ? -INFINITY : INFINITY;
                       
            if (num < target)
                lo = mid + 1;
            else if (num > target)
                hi = mid;
            else
                return mid;
        }
        return -1;
    }

  • 8
    F

    Thanks Stefan for the explanation, you're always the best.


  • 2
    N

    Wow, this is the true solution.


  • 2
    J

    It can be a follow up of find minimum in rotated array -:)


  • 1
    M

    thumb up!very clever solution.


  • 4
    D

    Java version

    public int search(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            
            int num = nums[mid];
            // If nums[mid] and target are "on the same side" of nums[0], we just take nums[mid].
            if ((nums[mid] < nums[0]) == (target < nums[0])) {
                num = nums[mid];
            } else {
                num = target < nums[0] ? Integer.MIN_VALUE : Integer.MAX_VALUE;
            }
    
            if (num < target)
                lo = mid + 1;
            else if (num > target)
                hi = mid - 1;
            else
                return mid;
        }
        return -1;
    }

  • 2
    L

    Inspired by this and @StefanPochmann work here: https://discuss.leetcode.com/topic/34467/pretty-short-c-java-ruby-python

    We can also view the array as already sorted with the following transformation:

    tuple: (value less than nums[0]?, value)
    [1,2,3,4,5] -> [(0,1), (0,2), (0,3), (0,4), (0,5)]
    [5,1,2,3,4] -> [(0,5), (1,1), (1,2), (1,3), (1,4)]
    

    Then we can use our standard binary search like so:

        def search(self, nums, target):
            N, t = nums, target
            i = bisect.bisect_left([(x < N[0], x) for x in N], (t < N[0], t))
            return i if t in N[i:i+1] else -1
    

    But that's already O(n) for the transform so ...:

        def search(self, nums, target):
            lo, hi, t = 0, len(nums) - 1, (target < nums[0], target)
            while lo <= hi:
                mid = (lo + hi) // 2
                guess = (nums[mid] < nums[0], nums[mid])
                if   guess == t: return mid
                elif guess < t:  lo = mid + 1
                else:            hi = mid - 1
            return -1
    

  • 1
    S

    you always make it clear, 3ku


  • 1

    Rewrite Stefan's algorithm in Java. Hope to make it a little simpler without losing its beauty.

        public int search(int[] nums, int target) {
            int n = nums.length; 
            if (n == 0) return -1; 
            
            int lo = 0, hi = n - 1, mid = 0, num = 0;  
            while (lo <= hi) { 
                mid = (lo + hi) >> 1;
                if (nums[mid] == target) return mid; 
                if ((nums[mid] < nums[0]) ^ (target < nums[0])) 
                    nums[mid] = target < nums[0]? Integer.MIN_VALUE : Integer.MAX_VALUE;  
                
                if (nums[mid] < target) lo = mid + 1; 
                else hi = mid - 1; 
            }
            
            return -1; 
        }

  • 1
    W

    @zzhai said in Clever idea making it simple:

    if ((nums[mid] < nums[0]) ^ (target < nums[0]))

    Great idea to use ^


  • -1
    Y

    Is there an assumption that the array doesn't contain repeated numbers? If the given array is [9, 2, 9, 9, 9, 9, 9] and the target is 2, this algorithm returns -1.


  • 0
    D

    @da.lin.1232 Hello,
    If we we are looking for Integer.MAX_VALUE, the result is wrong.
    I think Long is required.


  • 0
    Y

    @StefanPochmann Thanks for the explanation! It makes sense.
    I translated your code to python, but it doesn't seem to work (fails on case [3,1]
    ,3) Could you see why? Here's my code:

        def search(self, nums, target):
            low = 0
            high = len(nums)
            while low < high:
                #middle = low + (high - low)/2
                middle = (low + high) / 2
                current = nums[middle] if (nums[middle] > nums[0])==(target > nums[0]) else (-float('inf') if target < nums[0] else float('inf'))
                if current < target:
                    low = middle + 1
                elif current > target:
                    high = middle
                else:
                    return middle
            return -1
    
    

    Thanks.


  • 0
    O

    @yujiehuang get rid of else statement and insert the following right after you initialize middle--->
    if nums[middle]==target:return middle


  • 0
    G

    This is an excellent solution. The only problem is that it misses the case that one of the number in the array is actually -inf or inf. I am not a python expert, but in case of Java if you are using Integer.MAX_VALUE or Integer.MIN_VALUE, it will be a problem.


Log in to reply
 

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