2
\$\begingroup\$

The problem quoted:

https://leetcode.com/problems/single-element-in-a-sorted-array/

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

Example 1:

Input: [1,1,2,3,3,4,4,8,8]
Output: 2

Example 2:

Input: [3,3,7,7,10,11,11]
Output: 10

Note: Your solution should run in O(log n) time and O(1) space.


The answer:

var singleNonDuplicate = function(nums) {
    var low = 0, high = nums.length - 2, mid;

    while (low < high) {
        mid = low + Math.floor((high - low) / 2);
        if (mid % 2 === 1) mid--;           // make sure it is even

        if (nums[mid] !== nums[mid+1]) {    // the single element already happened on the left
            high = mid - 1;
        } else {
            low = mid + 2;
        }
    }
    return nums[low];
};

The fourth line:

while (low < high) {

if changed to

while (low <= high) {

can also pass all tests on the website. But which version is correct or more robust?

I also had to decide whether it is better to set the initial high to

high = nums.length - 2

or to

high = nums.length - 1

The same with

high = mid - 1;

I wonder if it is best to set it to mid - 1 or mid - 2.

It seems it can be complicated near the "end game", when there are 3, 5, 7, 9 remaining array elements, when the mid, low, high can be calculated in the way that the loop will not terminate or find the incorrect answer. If there are many elements remaining, such as 21, 31, etc, the algorithm in general works. It seems you have to consider the small cases when the number of remaining elements is small.

\$\endgroup\$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.