Big O notation for finding duplicates in a list using binary search
I have two different points:


As for complexity of your algorithm I believe this still to be O(N*log N). Consider the first half of the checks. For each check you do a binary search over the list of the size at least N/2 so it is O(log (N/2)) but given that log (N/2) = log(N) + constant it is just O(log N). And you do at least N/2 such checks. So it is O(N*log N)
If your list is not sorted, just sorting it to use binary search will take at least O(N*log N) so this is the lower bound anyway. And if it is sorted, your algorithm is very inefficient. You can do it in just O(N) by comparing each 2 sequential elements in the list (duplicates obviously have to be next to each other in a sorted list).