Binäre Suche nach Magic Index

Question

Ich übe binäre Suche und ich renne in eine Wand, wenn ich versuche, es zu implementieren, um den "magischen Index" in einem Array zu finden. Der magische Index ist A[i] == i.

Ich habe einige Implementierungen in Java using recursion gefunden, aber ich versuche, dies rekursiv zu vermeiden, weil Rekursion teuer ist (und ich möchte sehen, ob die binäre Suche hier geeignet ist).

Hier ist mein Code:

function magicIndex(arr) { 
    var result = arr, mid; 
    while (result.length > 1) { 
    mid = Math.floor(result.length/2); 

    if (result[mid] === mid) { 
     return arr.indexOf(result[mid]); 
    } else if (mid > result[mid]) { 
     result = result.slice(mid+1, result.length); 
    } else { 
     result = result.slice(0, mid); 
    } 
    } 
    return arr.indexOf(result.pop()); 
} 

Das Problem ist, dass der Algorithmus falsch das Array an der falschen Seite auf bestimmte Testläufe Scheiben schneiden.

Zum Beispiel gibt [-10, -3, 0, 2, 4, 8]4 zurück, aber [-10, 1, 0, 2, 5, 8] gibt auch 4 zurück.

Answer 1

Da Sie üben, denke ich, es ist gut für Sie, es selbst zu programmieren, aber ich gebe Ihnen eine Anleitung.

Mit diesem Algorithmus (Beachten Sie, dass die Eingabe-Array sollte bereits sortiert werden, da sonst eine Sortiermethode implementieren):

int arr[n]; 
    K ← 1; //search key 
    l ← 0; r ← n - 1; 
    while l ≤ r do 
     m ← floor((l + r)/2) 
     if K = arr[m] 
      return m 
     else if K < arr[m] 
      r ← m − 1 
     else 
      l ← m + 1 
    return −1 

Dies wird Ausgabe des Index Ihres Suchschlüssels, -1, wenn Schlüssel nicht gefunden wird.

Answer 2

Ihr zweites Array ist nicht sortiert und binary search funktioniert nur in einem sortierten Array.