Algorithmus zu finden, wenn es irgendein i so dass array [i] gleich i

Question

ich einen Auftrag von meinem CS Professor haben:

finden, in O (log n) Zeit, wenn in einer vorsortierten gegebenen Array von verschiedenen ganzen Zahlen gibt es einen Index i, so dass Array [i] = i. Beweisen Sie, dass die Zeit O (logn) ist.

Aktualisierung: Ganzzahl kann negativ, 0 oder positiv sein.

In Ordnung, also habe ich ein wenig damit gekämpft. Meine Idee ist dies:

Mit der binären Suche können wir nur sicher sein, dass es keinen solchen Wert links vom mittleren Element gibt, wenn array [mid] < = startindex, wobei mid der Index des mittleren Elements ist, und startindex ist der Anfang des Arrays.

Entsprechende Regel für die rechte Hälfte eines Arrays ist das Array [Mitte]> = Startindex + Numer, wobei Variablen wie oben und Numerisch die Anzahl der Elemente rechts von Mitte ist.

Das sieht nicht nach O (logn) aus, da ich im schlimmsten Fall die ganze Sache durchlaufen muss, oder? Kann mir hier jemand in die richtige Richtung zeigen oder mir sagen, dass das funktioniert?

Irgendwelche Ideen, wie ich das formell beweisen könnte? Ich frage nicht nach einer definitiven Antwort, sondern nach etwas Hilfe, um mich verständlich zu machen.

In C:

int _solve_prob_int(int depth, int start, int count, int input[]) 
    { 
    if(count == 0) 
     return 0; 
    int mid = start + ((count - 1)/2); 
    if(input[mid] == mid) 
     return 1; 

    if(input[mid] <= start && input[mid] >= start + count) 
     return 0; 

    int n_sub_elleft = (int)(count - 1)/2; 
    int n_sub_elright = (int)(count)/2; 

    if(input[mid] <= start) 
     return _solve_prob_int(depth + 1, mid + 1, n_sub_elright, input); 

    if(input[mid] >= start + count) 
     return _solve_prob_int(depth + 1, mid - n_sub_elleft, n_sub_elleft, input); 

    return _solve_prob_int(depth + 1, mid - n_sub_elleft, n_sub_elleft, input) || 
      _solve_prob_int(depth + 1, mid + 1, n_sub_elright, input); 
    } 

Ein Testfall:

Sorted args: 1 2 3 4 5 6 7 8 9 10 11 12 : 
Start: 0, count: 12, mid: 5 value: 6 
    Start: 0, count: 5, mid: 2 value: 3 
     Start: 0, count: 2, mid: 0 value: 1 
      Start: 1, count: 1, mid: 1 value: 2 
     Start: 3, count: 2, mid: 3 value: 4 
      Start: 4, count: 1, mid: 4 value: 5 
    Start: 6, count: 6, mid: 8 value: 9 
     Start: 6, count: 2, mid: 6 value: 7 
      Start: 7, count: 1, mid: 7 value: 8 
     Start: 9, count: 3, mid: 10 value: 11 
      Start: 9, count: 1, mid: 9 value: 10 
      Start: 11, count: 1, mid: 11 value: 12 

Die oben ist mein Programm mit einigen Ausgang laufen nach wie es gesucht. Bei einer Liste von 1 - 12 dreht es sich um den Index 5 und stellt fest, dass bei den Indizes 0 bis 4 ein Wert zwischen 0 und 4 liegen kann. Es bestimmt auch, dass es einen Wert zwischen 6-11 bei den Indizes 6-11 geben könnte. So fahre ich fort, sie beide zu suchen. Ist das falsch?

Answer 1

Die ganze Zahl wird unterschieden und sortiert.

Gegeben, dass array[i] = i Sie array[i] - i = 0 haben.

für jedes j i < Sie array[j] - j <= 0 und j haben> i müssen Sie array[j] - j >= 0 weil j von 1 in jeder Stufe, aber array [j] variieren variieren von mindestens 1 (distinct und sortiert Zahlen).

Also auf der linken Seite ist es <=0 auf der rechten Seite ist es >= 0.

Mit Dichotomie können Sie leicht die richtige Position in O(log n) finden.

---

Bitte beachten Sie, dass Sie nur ein Element finden müssen, nicht alle. In Ihrem Beispiel funktionieren alle Elemente, aber Sie benötigen nur eines von ihnen. Wenn Sie alle drucken möchten, wird es O(n) ..

Answer 2

Ihre Intuition ist richtig, die binäre Suche zu verwenden; Ihre Analyse ist nicht. Denken Sie daran, dass es sich um eine sortierte Liste handelt. In der binären Suchbedingung müssen Sie daher MAXIMUM von log (n) -Einträgen durchsuchen.

Answer 3

Denken Sie an eine binäre Suche wie ein Wort im Wörterbuch nachschlagen.Sie können beginnen, indem Sie das Buch genau in der Mitte des Wörterbuchs öffnen und sehen, ob das Wort oben auf der Seite vor, nach oder gleich dem gesuchten Wort ist. Wenn es danach ist, teilen Sie die zweite Hälfte des Wörterbuchs in zwei Teile und überprüfen Sie die Mitte dieser Hälfte. Nachdem Sie auf den oberen Rand der Seite geschaut haben, haben Sie den Bereich, nach dem Sie suchen, in etwa einem Viertel des Wörterbuchs eingegrenzt. Sie setzen diesen Prozess fort, bis Sie feststellen, dass das Wort irgendwo auf der Seite ist, die Sie betrachten. Dann verwenden Sie einen ähnlichen Prozess, um das Wort auf dieser Seite zu finden.

Dieser Prozess ist nicht O (n), weil Sie nicht jedes Wort auf jeder Seite selbst im schlimmsten Fall betrachten müssen. Es ist O (log n), weil Sie mit jedem Schritt ungefähr die Hälfte des Wörterbuchs als nicht mit dem gesuchten Wort löschen konnten.

bearbeiten

Sorry, falsch verstanden ich das ursprüngliche Problem. Der Schlüssel ist in diesem Fall das sogenannte "Taubenschlag-Prinzip", das besagt, dass Sie nur so viele Tauben in Löcher bohren können, wie Löcher vorhanden sind, in die sie passen. (Lassen Sie es bis zu.) Wissenschaft zu kommen mit einem Namen für eine so einfache Idee)

Betrachten Sie den folgenden Fall:

0 1 2 3 4 5 6 

Hier allearray[i] zu i gleich sind, so dass, wenn Sie zuerst Ihre binäre Suche beginnen, Sie werden sofort eine positive Antwort haben.

Lassen Sie uns jetzt eine Reihe weg von der Unterseite:

0 1 3 4 5 6 

Wenn Sie Ihre binäre Suche tun, werden Sie, dass array[3] > 3 finden, und Sie können richtig ableiten, dass kein Wert oberhalb dieser Drehpunkt möglicherweise machen könnte . Dies liegt daran, die Liste geordnet ist und einzigartig, so kann man nicht mit Kombinationen wie diese am Ende:

0 1 3 4 5 5 6 
0 1 3 4 6 5 7 

Sobald array[i] bestimmt wird, größer ist als i, es gibt einfach nicht genug Zahlen zwischen i und jedem gegeben n, damit das nächste Element im Array näher an i kommt. Ebenso, wenn Sie feststellen, dass array[i] weniger als i ist, haben Sie nicht genügend "Lücken" verfügbar, um "i" nachzuholen, während Sie auf den Anfang des Arrays schauen.

Daher können Sie bei jedem Schritt die Hälfte des Arrays korrekt eliminieren und, genau wie in einem Wörterbuch, bestimmen, ob in O (log n) Zeit ist.

Answer 4

Ich werde nicht versuchen, die Antwort zu geben weg, aber ich werde ein paar Beobachtungen weisen darauf hin:

Wenn das mittlere Element der Prüfung gibt es 3 Fälle. Das erste ist natürlich das Array [i] == i, in welchem ​​Fall der Algorithmus endet. In den anderen beiden Fällen können wir sowohl das Element selbst als auch etwa die Hälfte der Eingabe verwerfen.

Wenn nun Array [i]> i, ist es möglich, dass der Array-Index (i) mit den Array-Werten "nachholt", wenn wir uns nach rechts bewegen? Berücksichtigen Sie die sortierten unterschiedlichen Eigenschaften der Array-Werte.

Answer 5

Dies ist ein binäres Suchproblem mit Schlüssel nicht gegeben. In der Frage von OP ist der Schlüssel Mitte selbst! Suchen Sie in jedem Subarray nach einem mittleren Element.

Pseudocode der Lösung Binary Suche mit:

while (low and high don't meet) 
     mid = (low + high)/2 
     if (arr[mid] < mid) 
      high = mid - 1 
     else if (arr[mid] > mid) 
      low = mid + 1 
     else // we found it! 
      return mid; 
    // end while 
    return -1; // indicates there is no such i 

Answer 6

seit Array A sortiert. A [i]> = A [i-1] +1 => A [i] -i> = A [i-1] - (i-1), sei B [i] = A [i] -i, B [] ist ein sortiertes Array, in dem mittels Binärsuche nach B [x] == 0 gesucht werden kann.

Answer 7

Array B[i] = A[i]-i auch wenn A möglicherweise nicht sortiert [i] sortiert ist, aber Duplikate:

dieses Beispiel vor:

i: 0 1 2 3 4
A: 1 1 2 4 4

B [0] = a [0] = 1 -0, B [1] = A [1] -1 = 0, ...

B: 1 0 0 1 0

Answer 8

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

    if (end < start || start < 0 || end >= array.length) { 
     return -1; 
    } 
    int midIndex = start +(end-start)/ 2; 
    int midValue = array[midIndex]; 
    if (midValue == midIndex) {//trivial case 
     return midIndex; 
    } 
    // if there are duplicates then we can't conclude which side (left or right) will 
    // have the magic index. so we need to search on both sides 
    //but, we can definitely exclude few searches. 
    // take the example of the array : 
    // 0 1 2 3 4 5      6 7 8 9 10 -> indices 
    // -10, -5, 2, 2, 2, 3(midVal, midIndex = 5), 4, 7, 9, 12, 13 -> array element 
    // here, midValue < midIndex, but we can't say for sure which side to exclude 
    // as you can see there are two such magic indices. A[2] = 2 and A[7] = 7. so 
    // we need to search both sides 
    // since midValue < midIndex, then we can be sure that between index can't be 
    // between index number midValue and midIndex-1 

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

    /* Search right */ 
    int rightIndex = Math.max(midIndex + 1, midValue); 
    int right = fixedPoint(array, rightIndex, end); 

    return right; 
} 

public static int fixedPoint(int[] array) { 
    return fixedPoint(array, 0, array.length - 1); 
}