-1

I've a sorted array but it's not necessarily sequential, and I need to know IF it contains any duplicates. 

Array : | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 8 | 8 |

I know we can linearly traverse in O(n) check if it contains any duplicates, but I was wondering if it is possible using Binary Search.

martian_hunter
  • 11
  • 4
  • possible duplicate of [Binary Search O(log n) algorithm to find duplicate in sequential list?](http://stackoverflow.com/questions/12372385/binary-search-olog-n-algorithm-to-find-duplicate-in-sequential-list) – Raman Jul 09 '15 at 15:15
  • No way you can do it in less than O(N) – Eugene Sh. Jul 09 '15 at 15:15
  • 2
    @ARBY The requirement of "not necessarily sequential" is invalidating the answers in the linked question. Otherwise it can be done even in O(1) – Eugene Sh. Jul 09 '15 at 15:17

1 Answers1

0

No, You can't do it with binary search. All algorithms will take at least linear time.

Raman
  • 2,735
  • 1
  • 26
  • 46
  • Thanks :) I've one more question. If I were to run two parallel search pointers on same array (one from beginning and one from end), would that be less than a O(n) search, since I'm scanning two halves at same time. – martian_hunter Jul 09 '15 at 15:32
  • O(n/2)=O(n). Constant factors are irrelevant for big-O notation. – Eugene Sh. Jul 09 '15 at 15:33