Pretty short C++/Java/Ruby/Python


  • 36

    Explanation below the codes.

    Ruby:

    def search(nums, target)
      i = (0...nums.size).bsearch { |i|
        (nums[0] <= target) ^ (nums[0] > nums[i]) ^ (target > nums[i])
      }
      nums[i || 0] == target ? i : -1
    end
    

    Ruby Golf, just once for fun:

    def search(n, t)
      i=(0...n.size).bsearch{|i|(n[0]<=t)^(n[0]>n[i])^(t>n[i])};n[i||0]==t ?i:-1
    end
    

    Python:

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

    Python using bisect:

    class Solution:
        def search(self, nums, target):
            self.__getitem__ = lambda i: \
                (nums[0] <= target) ^ (nums[0] > nums[i]) ^ (target > nums[i])
            i = bisect.bisect_left(self, True, 0, len(nums))
            return i if target in nums[i:i+1] else -1
    

    C++:

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

    Java:

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

    Explanation

    My solutions use binary search guided by the following thoughts:

    Remember the array is sorted, except it might drop at one point.

    • If nums[0] <= nums[i], then nums[0..i] is sorted (in case of "==" it's just one element, and in case of "<" there must be a drop elsewhere). So we should keep searching in nums[0..i] if the target lies in this sorted range, i.e., if nums[0] <= target <= nums[i].

    • If nums[i] < nums[0], then nums[0..i] contains a drop, and thus nums[i+1..end] is sorted and lies strictly between nums[i] and nums[0]. So we should keep searching in nums[0..i] if the target doesn't lie strictly between them, i.e., if target <= nums[i] < nums[0] or nums[i] < nums[0] <= target

    Those three cases look cyclic:

        nums[0] <= target <= nums[i]
                   target <= nums[i] < nums[0]
                             nums[i] < nums[0] <= target
    

    So I have the three checks (nums[0] <= target), (target <= nums[i]) and (nums[i] < nums[0]), and I want to know whether exactly two of them are true. They can't all be true or all be false (check it), so I just need to distinguish between "two true" and "one true". Parity is enough for that, so instead of adding them I xor them, which is a bit shorter and particularly helpful in Java and Ruby, because those don't let me add booleans but do let me xor them.

    (Actually while developing this I thought of permutations of nums[0], target and nums[i] and the permutation parity and saw those three checks as representing inversions, but I had trouble putting that into words and now find the above explanation much better. But it helped me get there, so I wanted to mention it here.)


  • 0
    S

    Brilliant solution! I also learn from your clear explanation :)
    I have a short question if you don't mind, why do we need lo == hi in the return if lo < hi in while loop? (Java)


  • 0
    S

    @sweetteaoh Because when nums is empty, if you don't check this condition then you will return index 0.


Log in to reply
 

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