Simple JAVA binary search solution, with example step by step analysis


  • 0
    P
    class Solution {
        // binary search
        // [3,3,7,7,10,11,11] l: 0 r: 6 m: 3
        // [3,3,7,7,10,11,11] l: 4 r: 6 m: 5
        // [3,3,7,7,10,11,11] l: 4 r: 4 m: 5
        public int singleNonDuplicate(int[] nums) {
            if(nums == null || nums.length == 0) return -1;
            if(nums.length == 1) return nums[0];
        
            int left = 0;
            int right = nums.length - 1;
            
            while(left <= right && left >= 0 && right < nums.length) {
                int mid = left + (right - left) / 2;
                
                if(((mid - 1) >= 0 && nums[mid - 1] == nums[mid]) || ((mid + 1) < nums.length && nums[mid + 1] == nums[mid])) {
                    if(nums[mid - 1] == nums[mid]) {
                        if((mid + 1 - left) % 2 == 0){
                            left = mid + 1;
                        } else {
                            right = mid - 2;
                        }
                    } else {
                        if( (mid - left) % 2 == 0) {
                            left = mid + 2;
                        } else {
                            right = mid - 1;
                        }
                    }
                } else {
                    return nums[mid];
                }
            }
            
            return nums[left];
        }
    }
    

Log in to reply
 

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