Finding A [i] = i in einem sortierten Array mit Dubletten

Question

eine sortierte Array von ganzen Zahlen Gegeben mit möglicherweise dupliziert, wie Sie einen Index i so finden Sie, dass A[i]=i

Dies ist ein Problem in einem der Programmierbücher, die ich lese (Cracking the code interview). Die Lösung wird wie folgt umrissen:

public static int magicFast(int[] array, int start, int end) { 

    if (end < start || start < 0 || end >= array.length) { 
    return -1; 
    } 

    int midlndex = (start + end)/2; 
    int midValue = array[midlndex]; 
    if (midValue == midlndex) { 
     return midlndex; 
    } 

    /* Search left */ 
    int leftlndex = Math.min(midlndex - 1, midValue); 
    int left = magicFast(array, start, leftlndex); 
    if (left >= 0) { 
    return left; 
    } 

    /* Search right */ 
    int rightlndex = Math.max(midlndex + i, midValue); 
    int right = magicFast(array, rightlndex, end); 
    return right;  
} 

Der Autor äußert sich nicht zur Zeitkomplexität. Dies scheint jedoch eine O (n) -Lösung zu sein, da wir beide Seiten des "mittleren" Punktes betrachten müssen, im Gegensatz zu dem Problem, bei dem Array-Elemente verschieden sind. Die Rekursionsbeziehung ist T (n) = 2T (n/2) + c (c - konstante Zeit, um zu prüfen, ob das mittlere Element die Antwort ist)

Wie ist das besser als ein einfacher linearer Scan dann? Dies erscheint übermäßig kompliziert, nur um lineare Zeiteffizienz zu erreichen. Fehle ich hier etwas?

Answer 1

Nein, Sie verpassen nichts. Es gibt einen Kurzschluss für den ersten Zweig, aber der schlimmste Fall ist, dass beide Anrufe getätigt werden, was zu einer linearen Zeitwiederholung führt.

In der Tat hat dieses Problem keinen Sublinear-Time-Algorithmus durch eine einfache untere Grenze der Zellsonde. Betrachten wir die Familie von Arrays a wo

a(i) = i + 1 for i ≠ j 
a(j) = j 

für einige j. Diese Arrays sind nur unterscheidbar, indem der spezifische Eintrag, der der feste Punkt ist, untersucht wird, was eine untere Grenze von n - 1 Sonden bedeutet.

Die ursprüngliche CTCI-Frage, die ich annahm, erlaubte keine Duplikate - dann ist das modifizierte Array a(i) - i nicht abnehmend, was eine binäre Suche nach dem Nullelement ermöglicht.