If I have a sorted list of integers where every element except one is repeated, how would I find the singleton element in less than O(n) time?
For example: (−2, −2, 5, 5, 5, 67, 67, 72, 80, 80, 80, 80) would return 72.
I'm fairly certain binary search is involved in this, but not sure how to implement it. I'm just looking for the pseudocode here.
I'm thinking to iterate through the list, and binary search for the last occurrence of the current element. If the index of that is the same as the one we're currently on, that's the singleton element. If not, keep going. That would be O(nlogn) I think.
If each integer can be repeated an arbitrary number of times, the best algorithm would be O(n) as there is no way to avoid iterating through every integer. Simply iterate through the list and keep a counter of how many of the same integer has been found in a row. If the counter is only one and a new integer is discovered, then terminate, as we have found the non-repeating integer.
If we know that all numbers are repeated the same number of times (except for the one which is not repeated), we can use binary search to achieve even better time complexity. However, based on your example problem, it looks like this is not the case.