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


  • 25
    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?


Log in to reply
 

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