Java Binary Search


  • 0
    H

    The idea is to find the middle, if left part is odd, the single number is in the left part. Otherwise, it is in the right part

    
    public class Solution {
        public int singleNonDuplicate(int[] nums) {
            int left = 0;
            int right = nums.length - 1;
            int len = right;
            if (right == 1) {
                return nums[0];
            } 
            while (left <= right) {
                int middle = (left + right) >>>1;
                // update middle.
                if (middle > 0 && nums[middle] == nums[middle - 1]) {
                    
                } else if (middle < len && nums[middle] == nums[middle + 1]) {
                    middle++;
                } else {
                    return nums[middle];
                }
                if ((len - middle) %2 == 0) {
                    right = middle - 1;
                } else {
                    left = middle + 1;
                }
            }
            return nums[left];
        }
    }
    

Log in to reply
 

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