Java Code by using binary search O(log(n))


  • 13
    D

    public int singleNonDuplicate(int[] nums) {
    int low = 0;
    int high = nums.length-1;

        while(low < high) {
            int mid = low + (high - low)/2;
            if(nums[mid] != nums[mid+1] && nums[mid] != nums[mid-1])
                return nums[mid];
            else if(nums[mid] == nums[mid+1] && mid % 2 == 0)
                low = mid+1;
            else if(nums[mid] == nums[mid-1] && mid % 2 == 1)
                low = mid+1;
            else
                high = mid-1;
        }
        return nums[low];
    }

  • 0
    L

    Why mid = low + (high-low)/2?


  • 2
    D

    @leap20 : Its basically to avoid the integer overflow. Normal mid calculation could result in sum being greater than 2^31-1. This avoids that.


  • 0
    V
    This post is deleted!

  • 1
    M

    you solution will fail for following ex; [1, 2, ,2, 3, 3] with index out of bounds. simple fix - check for mid == 0.


  • 0
    Y

    @mdwadhwani I agree with you. But it passed the all the test cases. With the below code, the edge cases are considered, but it's a little tedious.

        public int singleNonDuplicate(int[] nums) {
            int n = nums.length;
            int l = 0;
            int r = n - 1;
            
            while (l <= r) {
                int m = l + (r - l) / 2;
                
                if (m == 0) {
                    if (nums[0] == nums[1])
                        l = 2;
                    else
                        return nums[0];
                } else if (m == n - 1) {
                    if (nums[n - 1] == nums[n - 2])
                        r = n - 3;
                    else
                        return nums[n - 1];
                } else if ((nums[m] != nums[m - 1]) && (nums[m] != nums[m + 1])) {
                    return nums[m];
                } else if (nums[m] == nums[m - 1]) {
                    if ((n - m - 1) % 2 == 1)
                        l = m + 1;
                    else
                        r = m - 2;
                } else {
                    if (m % 2 == 1)
                        r = m - 1;
                    else
                        l = m + 2;
                }
            }
            
            return nums[l + 1];
    }
    

  • 0
    K

    @leap20 This is the same as (low+high)/2 but it avoids the overflow error if numbers are too large.


  • 1
    I
    return nums[low];
    

    whats this line of code for? usually the successful termination of search happens inside the loop. if it exits the loop without returning anything, it usually means it didnt find a match. I didn't understand what case this return statement addresses. appreciate any help - thanks!

    Update:
    never mind, i figured out the case where its required. when the first or last element is the answer, the search terminates unsuccessfully, but since we know the array contains an answer (element occurring once) we blindly return it at that point.
    Example inputs: [1,1,2] or [1,2,2]


  • 0
    N

    You can simplify this further by following the invariant - the duplicate element is always on the right side of the binary search.

      public int singleNonDuplicate(int[] nums) { 
        int low = 0, high = nums.length - 1;
        while(low < high) {
          int mid = (low + high)/2;
          if(mid%2 == 0 && nums[mid] == nums[mid+1]) 
            low = mid + 1;
          else if(mid%2 != 0 && nums[mid-1] == nums[mid])
            low = mid + 1;
          else 
            high = mid;
        }
        return nums[low];
      }
    

  • 0

    To Avoid: ArrayIndexOutOfBoundsException:

    public class Solution {
        public int singleNonDuplicate(int[] nums) {
            if(nums==null || nums.length %2 ==0) return Integer.MIN_VALUE;
            int len = nums.length, left =0, right = len-1;
            while (left <= right){
                int mid = left + (right-left)/2;
                if(mid ==0 || mid == len -1 || (nums[mid]!=nums[mid-1] && nums[mid]!=nums[mid+1])) 
                    return nums[mid];
                int firstMidVal = nums[mid] == nums[mid-1] ? mid-1 : mid;
                if ((firstMidVal-left) % 2 == 0) left = firstMidVal +2;
                else right = firstMidVal-1;
            }
            return Integer.MIN_VALUE;
        }
    }
    

  • 0
    P

    @inswingingyorker I have the same line in my code it is for the case when the single element is the last element..see this test case
    [3,3,7,7,8,8,10,10,11]
    Hope this helps.. Correct me if i am wrong


Log in to reply
 

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