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


  • 36
    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

    @sha256pki you can look at it this way: if the middle index is an odd number then by the problem definition all elements in the lower half should appear twice. Example:

    index:   0  1  2  3
    array:  [1, 1, 2, 2, ...]
    mid: 3
    

    So we check if array[2] == array[3]. If this condition is True we know the single number has got to be in upper half of the array. Else look at lower half.

    Finally, when the invariant start < end is False we know we've found the answer. I hope this helps.


Log in to reply
 

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