Binary-search with duplicate elements in array

Question

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.

Do you mean with "sequential list" that all numbers in the range must be present? — Henry
– Henry, Commented Oct 5, 2020 at 13:36
I know the way with simple loop to find the 4. but I want to do it by binary-search :) — ReoL
– ReoL, Commented Oct 5, 2020 at 13:44
@GiorgiTsiklauri That's the inverse of this question... but yes, op isn't very clear in the description. — user202729
– user202729, Commented Oct 5, 2020 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
– Giorgi Tsiklauri, Commented Oct 5, 2020 at 13:50

user202729 · Accepted Answer · 2020-10-05 13:56:08Z

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.

answered Oct 5, 2020 at 13:56

user202729

4,2093 gold badges31 silver badges48 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

ReoL Over a year ago

You means it can't exist?

mighty_dev · Accepted Answer · 2020-10-05 17:17:13Z

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

Collectives™ on Stack Overflow

Binary-search with duplicate elements in array

2 Answers 2

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related