Jose - 9 months ago 48

Javascript Question

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

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.

Source (Stackoverflow)