Binäre Suche nicht ausgeführt?

Question

Ich habe versucht, den binären Suchalgorithmus in meinem Codebeispiel zu verwenden, aber es läuft nicht wie erwartet. Ich weiß nicht warum. Bitte erläutern Sie mir

var array = [1, 4, 6, 8, 9, 12, 15, 17, 19, 34, 55, 78, 80]; 

function binarySearch (array, numberToSearch) { 
var firstIndex = 0; 
var lastIndex = array.length - 1; 
var currentIndex; 
var currentElement; 

currentIndex = (lastIndex + firstIndex)/2 | 2; 
currentElement = array[currentIndex]; 

while (firstIndex <= lastIndex) { 
    if (numberToSearch === currentElement) { 
     // found 
     console.log(currentIndex); 
     return currentIndex; 
    } else if (numberToSearch < currentElement) { 
     lastIndex = currentIndex - 1; 
     currentIndex = (lastIndex + firstIndex)/2 | 2; 
     currentElement = array[currentIndex]; 
    } else if (numberToSearch > currentElement) { 
     firstIndex = currentIndex + 1; 
     currentIndex = (lastIndex + firstIndex)/2 | 2; 
     currentElement = array[currentIndex]; 
    } 
} 
return -1; 
} 
binarySearch(array, 12); 

Ich drucke sollte: 5, aber nichts passiert

Answer 1

Was mit Ihrem Code falsch ist:

1. Es sollte var currentIndex = (lastIndex + firstIndex)/2 | 0; (nicht | 2);

2. currentIndex und currentElement sollte bei jeder Iteration innerhalb der Schleife berechnet werden.

Also, das ist die korrigierte Version des Codes:

var array = [1, 4, 6, 8, 9, 12, 15, 17, 19, 34, 55, 78, 80]; 
 

 
function binarySearch (array, numberToSearch) { 
 
var firstIndex = 0; 
 
var lastIndex = array.length - 1; 
 

 
while (firstIndex <= lastIndex) { 
 
    var currentIndex = (lastIndex + firstIndex)/2 | 0; 
 
    var currentElement = array[currentIndex]; 
 
    if (numberToSearch === currentElement) { 
 
     return currentIndex; 
 
    } else if (numberToSearch < currentElement) { 
 
     lastIndex = currentIndex - 1; 
 
    } else if (numberToSearch > currentElement) { 
 
     firstIndex = currentIndex + 1; 
 
    } 
 
} 
 
return -1; 
 
} 
 

 
console.log(binarySearch(array, 99)); // -1 
 
console.log(binarySearch(array, 12)); // 5

BTW, das var currentIndex = (lastIndex + firstIndex)/2 | 0; sieht ganz ungewöhnlich. Der gemeinsame Weg ist var currentIndex = Math.floor((lastIndex + firstIndex)/2);

Answer 2

Zunächst einmal, was der Punkt der bitweise ist OR hier:

currentIndex = (lastIndex + firstIndex)/2 | 2; 

denke ich es sein sollte:

currentIndex = (lastIndex + firstIndex)/2; 

Es gibt grundlegende Fehler auf der Suche Speicherplatzupdate. Wenn numberToSearch < currentElement bedeutet das middle element (Element bei Index Momentan) größer ist als Nummer gesucht werden daher richtig neue Grenzen sind:

lastIndex = currentIndex - 1; 

Auch wenn numberToSearch > currentElement bedeutet das middle element (Element bei Index Momentan) ist kleiner als zu durchsuchende Anzahl, daher richtig neue Grenzen sind:

firstIndex = currentIndex + 1; 

Daher

, der richtige Code ist:

var array = [1, 4, 6, 8, 9, 12, 15, 17, 19, 34, 55, 78, 80]; 

function binarySearch (array, numberToSearch) { 
var firstIndex = 0; 
var lastIndex = array.length - 1; 
var currentIndex; 
var currentElement; 

currentIndex = (lastIndex + firstIndex)/2; 
currentElement = array[currentIndex]; 

while (firstIndex <= lastIndex) { 
    if (numberToSearch === currentElement) { 
     // found 
     console.log(currentIndex); 
     return currentIndex; 
    } else if (numberToSearch < currentElement) { 
     lastIndex = currentIndex - 1; 
     currentIndex = (lastIndex + firstIndex)/2 | 2; 
     currentElement = array[currentIndex]; 
    } else if (numberToSearch > currentElement) { 
     firstIndex = currentIndex + 1; 
     currentIndex = (lastIndex + firstIndex)/2 | 2; 
     currentElement = array[currentIndex]; 
    } 
} 
return -1; 
} 
binarySearch(array, 12); 

Answer 3

Hier ist Ihre korrigierte Antwort mit all den Orten, die ich aktualisiert. Du warst ziemlich nah dran! Es schien, als ob Sie die iterative Version von Binary Search mit der recursive Lösung kombinierten.

CodePen Demo

var array = [1, 4, 6, 8, 9, 12, 15, 17, 19, 34, 55, 78, 80]; 

function binarySearch (array, numberToSearch) { 
    var firstIndex = 0; 
    var lastIndex = array.length - 1; 
    var currentIndex; 
    var currentElement; 

    while (firstIndex <= lastIndex) { 
    currentIndex = (lastIndex + firstIndex)/2 | 0; //should default to zero, not Two! 
    currentElement = array[currentIndex];//These should both update every iteration so it does not infinitely loop! 
    if (numberToSearch === currentElement) { 
     // found 
     console.log(currentIndex); 
     return currentIndex; 
    }else if (numberToSearch < currentElement) { 
     lastIndex = currentIndex - 1; //If current is too big, move right pointer to the left 
    }else if (numberToSearch > currentElement) { 
     firstIndex = currentIndex + 1;//If current is too small, move left pointer to the right 
    } 
    } 
    return -1;//When condition of while it broken and no solution has been found, return -1 to indicate it is not in the array 
} 
binarySearch(array, 12) //5 

wird weiter durch optimiert nicht mit Math.floor() als number | 0is sometimes faster.