Hi all,
i have recently seen this question. I am not understanding the binary search approach given there. it is said that if mid is even, a[mid] and a[mid+1] are the same, then the odd repeating element is after mid. i didn’t get how we reach this conclusion. can anyone explain me this?
The reason this approach is viable is because of the highly structured data. Effectively the whole array of values is a series of pairs of values, always moving to a new value after each pair, except in one instance somewhere there is a solo value instead of a pair. Clearly the array is odd length, so the middle value, if it’s not the solo value, is either paired up with the preceding value or with the succeeding value. Then, if you split the array by removing this pair, you can see which part is odd length and look for the solo value in that half of the array in the same way.