0

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?

Jose
  • 4,880
  • 8
  • 27
  • 49
  • 1
    And you know ahead of time that 4 is the value that is duplicated? – hatchet - done with SOverflow Sep 18 '16 at 04:07
  • This cannot be done faster than O(n) if you don't have a specific value to search for. The worst case is that there are no duplicates, in which case you will always have to look at the entire array. – 4castle Sep 18 '16 at 04:08
  • This similar question may help (it is not a duplicate though, since its numbers are serial, with no gaps) as one of the answers mentions this case. http://stackoverflow.com/questions/9673658/in-less-than-linear-time-find-the-duplicate-in-a-sorted-array – hatchet - done with SOverflow Sep 18 '16 at 04:12
  • If you definitely have a "single" duplicate as mentioned in the topic (element being singular) you can definitely find it without iterating all items even if they are the last pair. – Redu Sep 18 '16 at 13:39

1 Answers1

2

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.

paxdiablo
  • 854,327
  • 234
  • 1,573
  • 1,953
  • That's what I thought. Yes, thank you. You're right, binary search needs something to search for (that was a *duh* moment). – Jose Sep 18 '16 at 04:22