Znajdź duplikat w tablicy kolejnych liczb całkowitych w czasie O (log n)

Question

Kilka dni temu, w wywiadzie, zostałem poproszony o program, który znalazłby pojedynczy duplikat elementu w kolejnej tablicy liczb całkowitych w czasie O(log n) .

Przypadek jest nieco specyficzny, ponieważ w sumie jest 11 liczb całkowitych (od 1 do 10, w tej kolejności) plus jeden duplikat dowolnej z tych liczb, wstawiony gdzieś pomiędzy.

dano próbkę podobną do tej:

{1, 2, 3, 4, 5, 6, , 7, 8, 9, 10}

Tak, teraz mam następujący kod C:

#include <stdio.h> 

int main (void) 
{ 
    int a[11] = {1, 2, 3, 4, 5, 6, 2, 7, 8, 9, 10}, first=0, last=10, mid; 

    while (1) 
    { 
     mid = (first + last)/2; 

     if (mid+1 == a[mid]) 
      first = mid+1; 

     else if ((mid == 0) || (mid == 10) || (a[mid+1] - a[mid-1] == 1)) /* Order is Important, (a[mid+1] - a[mid-1] == 1) must be last */ 
      break; 

     else 
      last = mid-1; 
    } 

    printf("Duplicate element is %d, located at position no. %d.", a[mid], mid+1); 

    return 0; 
} 

Czy to właściwie spełnia kryteria O(log n)? Czy są jakieś alternatywy/ulepszenia?

Answer 1

Tak, ma ona złożoność czasową O(log n).

Jest możliwe, aby kod bardziej jasne stosując następujący fakt: trzeba znaleźć najmniejszą i takie, że a[i] != i + 1, więc to może być realizowane w sposób bardziej zwięzły sposób:

//invariant: the [0...low] prefix does not contain a duplicate 
//   the [0...high] prefix contains a duplicate 
low = 0 //[0...0] prefix obviously does not contain a duplicate 
high = 10 //the entire array obviously contains a duplicate 
while high - low > 1: 
    mid = (low + high)/2 
    if a[mid] != mid + 1: 
     high = mid 
    else: 
     low = mid 
print(a[high], high) 

Answer 2

Możemy modyfikować binary search algorithm, aby uzyskać rozwiązanie. W binary search mamy klucz i użyliśmy tego klucza do znalezienia jego pozycji przez podzielenie rozmiaru tablicy. Tutaj nie mamy klucza, zamiast tego musimy go znaleźć. Ale zachowanie duplicate element może być używane do bisect rozmiaru tablicy. W jaki sposób ? pozwala zobaczyć:

Na uważnie patrząc dane, możemy łatwo zobaczyć, że po włożeniu duplikat elementu w dowolnej pozycji (słownie index) w kolejnych elementów tablicy własność elementów ulegnie zmianie (a[i] == i+1 ->a[i] != i+1) ze stanowiska index (w tym index). Teraz ta zmieniona właściwość może być użyta do podzielenia rozmiaru tablicy. Dlatego możemy znaleźć duplikat w O(log(n)).

Na przykład Zastanów się daną tablicę: {1, 2, 3, 4, 5, 6, 2, 7, 8, 9, 10}

{1, 2, 3, 4, 5, 6, 2, 7, 8, 9, 10} 
          || 
          from this position the the property of (a[i] == i+1) will no more satisfied. 

Ta nieruchomość może być model przepoławiać rozmiar tablicy w roztworze.

void binary_duplictae_finder(int a[], int low, int high) { 

    int mid=(low+high)/2; 

    if(high - low > 1){ 
      if(a[mid]!=mid+1) 
       binary_duplictae_finder(a, low, mid); 
      else 
       binary_duplictae_finder(a, mid, high); 
    } 

    if(high==low+1) 
     printf("%d ", a[high]); 
}