Java Binary Search, short (7l), O(log(n)) w/ explanations


  • 49
    T

    All credits go to @Penghuan who thought of using the pairs wisely.

    This method seems to be a bit simpler to understand, since it doesn't start with the left half and stays a little bit closer to the conventional solutions.

       public static int singleNonDuplicate(int[] nums) {
            int start = 0, end = nums.length - 1;
    
            while (start < end) {
                // We want the first element of the middle pair,
                // which should be at an even index if the left part is sorted.
                // Example:
                // Index: 0 1 2 3 4 5 6
                // Array: 1 1 3 3 4 8 8
                //            ^
                int mid = (start + end) / 2;
                if (mid % 2 == 1) mid--;
    
                // We didn't find a pair. The single element must be on the left.
                // (pipes mean start & end)
                // Example: |0 1 1 3 3 6 6|
                //               ^ ^
                // Next:    |0 1 1|3 3 6 6
                if (nums[mid] != nums[mid + 1]) end = mid;
    
                // We found a pair. The single element must be on the right.
                // Example: |1 1 3 3 5 6 6|
                //               ^ ^
                // Next:     1 1 3 3|5 6 6|
                else start = mid + 2;
            }
    
            // 'start' should always be at the beginning of a pair.
            // When 'start > end', start must be the single element.
            return nums[start];
        }
    

  • 0
    A

    @thms_la Awesome explanation!


  • 0
    R

    @thms_la thanks


  • 0
    P

    Great solution..Easy to understand..


  • 1
    S

    Can you help understand the idea here?

    So control lands up in the middle of array by (start+end)/2
    If the mid is not even, then it is turned even by moving to left - (why is it needed to be even? whats significance of mid as even index)?

    Once you're at even mid, compare if mid and mid+1 are same. If they're not, binary search in left part (why? what dictates left or right subarray search). If they're equal, so mid and mid+1 are same, then move to right subarray (again why?).

    Then return item at start

    Why is this working?


  • 0
    L

    @sha256pki The basic idea here is that there's only one element that appears once. Suppose a series of number that all the elements appear twice, then elements always change at even positions. If one element only appears once, then the rule will be broken and we can use binary search based on this rule.


  • 0
    A
    This post is deleted!

Log in to reply
 

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