Jose Jose - 1 year ago 71
Javascript Question

Finding the duplicate element in a (sorted) Array in less than O(n) time?

I'm wondering if it's possible to perform a Binary Search in O(log n) on a JavaScript Array to find a single duplicate element.

// Example
// Input: var arr = [1, 3, 4, 4, 6, 9, 11, 12, 14]
// Output: 4

I know how to solve this in linear time, but I've been trying to write a solution in O(log n) except I'm unsure of how to proceed in terms of reducing the chunk of the array to search on each iteration. Any advice?

Answer Source

Binary search only works if you know the element you're looking for (or, more exactly, if you can tell which half it's in when you've chosen your pivot point).

There is nothing in your question that seems to indicate you have this knowledge so, based on that, O(n) is the best you can currently do.

If there was some extra information, it may be possible, things like all the numbers in a range being represented except one, or the duplicate being in a specific range.

However, based on current information, that's not the case.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download