Java Binary Search O(log(n)) Shorter Than Others


  • 45
    P

    My solution using binary search. lo and hi are not regular index, but the pair index here. Basically you want to find the first even-index number not followed by the same number.

    public class Solution {
        public int singleNonDuplicate(int[] nums) {
            // binary search
            int n=nums.length, lo=0, hi=n/2;
            while (lo < hi) {
                int m = (lo + hi) / 2;
                if (nums[2*m]!=nums[2*m+1]) hi = m;
                else lo = m+1;
            }
            return nums[2*lo];
        }
    }
    

  • 0
    R

    very elegant solution. thank you


  • 0
    R
    This post is deleted!

  • 0
    G

    @rishavrastogi Given a sorted array consisting of only integers where every element appears twice except for one element which appears once. Find this single element that appears only once.


  • 0
    D

    So GREAT and concise!


  • 0
    S

    how do you get that? That's really wise!


  • 1

    Great execution. I did something similar in JavaScript:

    var singleNonDuplicate = function(nums) {
        let low = 0;
        let high = nums.length - 1;
        while (low < high) {
            let mid = Math.floor((low + high) / 2);
            let delta = mid % 2 ? -1 : 1;
            if (nums[mid] === nums[mid + delta]) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return nums[low] === nums[low - 1] ? nums[low + 1] : nums[low];
    };
    

  • 0
    T

    If you have a hard time understanding this solution's algorithm, I made another version based on his idea. Feel free to have a look at it :)


  • 0

    Thanks for sharing. I have a question, in a binary search problem, how do you know to determine the updating of hi and lo?

    For example, in regular binary search, we usually do something like hi = m - 1. But in your algorithm, the right updating for hi would be hi = m. I wonder if there is any rule of thumb that I can apply when designing a binary search variation problem or is it that you just have to try it out by cases? Thank you.


  • 0
    H

    @Penghuan I like your solution, especially your explanation, which told us everything about this problem.

    ... to find the first even-index number not followed by the same number.

    Your code is very concise, but not that easy to understand.

    Why not do it with a Standard Binary Search. >3<

    public class Solution {
            public int singleNonDuplicate(int[] nums) {
                int lo = 0, hi = nums.length-1;
                while (lo < hi) {
                    int mid = lo + (hi - lo) / 2;
                    int even = (mid % 2 == 0)? nums[mid] : nums[mid-1];
                    int followingOdd = (mid % 2 == 0)? nums[mid+1] : nums[mid];
                    if (even == followingOdd) {
                        lo = mid + 1;
                    } else {
                        hi = (mid / 2) * 2;
                    }
                }
                return nums[lo];
            }
    }
    

Log in to reply
 

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