In less-than-linear time, find the duplicate in a sorted array

Question

Today, an interviewer asked me this question. My immediate response was that we could simply do a linear search, comparing the current element with the previous element in the array. He then asked me how the problem could be solved in less-than-linear time.

Assumptions

• The array is sorted
• There is only one duplicate
• The array is only populated with numbers [0, n], where n is the length of the array.

Example array: [0,1,2,3,4,5,6,7,8,8,9]

I attempted to come up with a divide-and-conquer algorithm to solve this, but I'm not confident that it was the right answer. Does anyone have any ideas?

Answer 1

#include <bits/stdc++.h>
using namespace std;

int find_only_repeating_element(int arr[] , int n){
int low = 0;
int high = n-1;
while(low <= high){
    int mid = low + (high - low)/2;
    if(arr[mid] == arr[mid + 1] || arr[mid] == arr[mid - 1]){
        return arr[mid];
    }
    if(arr[mid] < mid + 1){
        high = mid - 2;
    }else{
        low = mid + 1;
    }
   }
   return -1;
}

int main(int argc, char const *argv[])
{
int n , *arr;
cin >> n;
arr = new int[n];
for(int i = 0 ; i < n ; i++){
    cin >> arr[i];
}
    cout << find_only_repeating_element(arr , n) << endl;
    return 0;
}

Answer 2

Can be done in O(log N) with a modified binary search:

Start in the middle of the array: If array[idx] < idx the duplicate is to the left, otherwise to the right. Rinse and repeat.

Answer 3

I attempted to come up with a divide-and-conquer algorithm to solve this, but I'm not confident that it was the right answer.

Sure, you could do a binary search.

If arr[i/2] >= i/2 then the duplicate is located in the upper half of the array, otherwise it is located in the lower half.

while (lower != upper)
    mid = (lower + upper) / 2
    if (arr[mid] >= mid)
        lower = mid
    else
        upper = mid-1

Since the array between lower and upper is halved in each iteration, the algorithm runs in O(log n).

ideone.com demo in Java

Answer 4

If no number is missing from the array, as in the example, it's doable in O(log n) with a binary search. If a[i] < i, the duplicate is before i, otherwise it's after i.

If there is one number absent and one duplicate, we still know that if a[i] < i the duplicate must be before i and if a[i] > i, the absent number must be before i and the duplicate after. However, if a[i] == i, we don't know if missing number and duplicate are both before i or both after i. I don't see a way for a sublinear algorithm in that case.