0

I want find if there is a single element in a list of duplicate elements.

For this code

private static int findDuplicate(int array[]) {
    int low = 0;
    int high = array.length - 1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        int midVal = array[mid];
        if (midVal == mid)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return high;
}

It find the duplicate number but I want to find only the single number in the duplicate and sorted array.

For example, given this int[] input:

[1,1,2,2,3,3,4,5,5]

Output would be '4'.

Or this int[] input:

[1,1,2,2,3,4,4,5,5,6,6]

Output would be '3'.

In this int[] input:

[1,1,2,7,7,9,9]

Output would be '2'.

I'm working in Java now but any language or psuedo-code is fine.

I know the obvious traversal at O(n) linear time, but I'm trying to see if this is possible via binary search at O(log n) time.

The elements are sorted and only duplicate twice! I know the way with simple loop but I want to do it by binary search.

rene
  • 41,474
  • 78
  • 114
  • 152
ReoL
  • 21
  • 5
  • Do you mean with "sequential list" that all numbers in the range must be present? – Henry Oct 05 '20 at 13:36
  • I know the way with simple loop to find the 4. but I want to do it by binary-search :) – ReoL Oct 05 '20 at 13:44
  • Does [this](https://stackoverflow.com/questions/12372385/binary-search-olog-n-algorithm-to-find-duplicate-in-sequential-list) answer your question? – Giorgi Tsiklauri Oct 05 '20 at 13:48
  • @GiorgiTsiklauri That's the inverse of this question... but yes, op isn't very clear in the description. – user202729 Oct 05 '20 at 13:49
  • @user202729 why is that an inverse? it says *find a duplicate with binary search in a sequential list* and that is what OP is looking for. – Giorgi Tsiklauri Oct 05 '20 at 13:50
  • @GiorgiTsiklauri See, in op's question all-but-one values are duplicated, while in the linked one only one is duplicated. Plus op doesn't ensure that numbers are sequential. – user202729 Oct 05 '20 at 13:56
  • Just start recursively splitting by an (even left) half. and check that the left, resp. right half does not end on a pair _xx_. – Joop Eggen Oct 05 '20 at 13:57
  • Please clarify your question. Example: what output do you expect when there are two entries that are unique? – GhostCat Oct 05 '20 at 13:59
  • @user202729 OP's example depicts it's sequential. In the OP's question the example is poorly provided.. as several matches can be considered *duplicates* (yet, I'm still unaware of what does OP mean - adjacent elements? or any duplicates?), and the link I provided just has an example with one duplicate.. details should be clarified in this post, but the essence of these two questions smells to be the same for me. – Giorgi Tsiklauri Oct 05 '20 at 14:01

2 Answers2

1

Consider each pair of 2 consecutive elements: (the pairs with 2 elements different are highlighted) (note that there's a stray element at the end)

(1 1) (2 2) (3 3) (4 5) (5 6) (6 7) (7 8) (8)

Observe that the only non-duplicated element will make the corresponding pair and all the later pairs have different values, the pairs before that have the same value.

So just binary search for the index of the different pair.

This algorithm also don't require that the list is sorted, only that there's exactly one element which appears once, and all other elements appear twice, in consecutive indices.

Special case: if the last element is the unique one, then all the pairs will have equal values.

user202729
  • 3,358
  • 3
  • 25
  • 36
0

Every pair of same values will be like below in terms of indices:

(0,1),
(2,3),
(4,5)
(6,7)

etc. You can clearly see that if index is even, check with next element for similarity. If index is odd, you can check with previous value for similarity. If this symmetry is broken, you can move towards left side or if everything is ok, keep moving right.

Pseudocode(not tested):

low = 0,high = arr.length - 1

while low <= high:
    mid = (low + high) / 2
    if mid == 0 || mid == arr.length - 1 || arr[mid] != arr[mid-1] and arr[mid] != arr[mid + 1]: // if they are corner values or both left and right values are different, you are done
        return arr[mid]
    if(mid % 2 == 0):
        if arr[mid + 1] != arr[mid]: // check with next index since even for symmetry
            high = mid
        else:
            low = mid + 2
    else:
        if arr[mid - 1] != arr[mid]: // check with prev index since odd for symmetry
            high = mid
        else:
            low = mid + 1

return -1
nice_dev
  • 17,053
  • 2
  • 21
  • 35