Detaillierte Erläuterung der Implementierungsmethode der Halbsuche in der JS-Array-Suche

In diesem Artikel wird hauptsächlich die Implementierungsmethode der Halbsuche in JSArraySuche vorgestellt und das Prinzip des Javascript-Array-Halbsuchalgorithmus in Kombination mit spezifischem analysiert Beispiele für Implementierungsfähigkeiten und zugehörige Hinweise, auf die sich Freunde in Not beziehen können

Dieser Artikel beschreibt die Implementierungsmethode der Halbsuche für die JS-Array-Suche. Teilen Sie es wie folgt mit allen als Referenz:

1. Methodenprinzip:

Bei der Suche nach einem bestimmten Wertwert aus einem bestimmten Sequenzarray arr Wann zu bestimmen ein Zwischenpunkt middle = Math.floor((end point - start point) / 2);

3. Vergleichen Sie unter der Prämisse startIndex < endIndex die Größe von arr[middle] und value:

(1) arr[middle] < value

Passen Sie den Suchbereich an die zweite Hälfte des Arrays an, d. h. startIndex = middle + 1, endIndex = arr.length -1;

(2) arr[middle] > value

Passen Sie den Suchbereich an die erste Hälfte des Arrays an, d. h. startIndex = 0, endIndex = middle - 1;

Dann berechne die Mitte neu und vergleiche erneut arr[middle] und value, bis sie gleich sind oder startIndex >= endIndex.

2. Code:

3. Vor- und Nachteile:

// 该例的写法适用于序列为由小到大的数组
function binarySearch(arr, value) {
  var startIndex = 0,
  endIndex = arr.length - 1;
  middle = Math.floor((endIndex - startIndex) / 2);
  while (arr[middle] !== value && startIndex < endIndex) {
    if (arr[middle] > value) {
      endIndex = middle - 1;
    } else if (arr[middle] < value) {
      startIndex = middle + 1;
    }
    middle = Math.floor((endIndex - startIndex) / 2);
  }
  return (arr[middle] !== value) ? -1 : middle;
}

(1) Vorteile: Bei jeder Suche wird die Anzahl der zu durchsuchenden Array-Elemente um die Hälfte reduziert Daher ist seine Leistung besser als die lineare Suchmethode (in Array-Elementen) Es ist besonders offensichtlich, wenn es mehr gibt);

(2) Nachteile:

gilt nur für Sequenzarrays. Bevor die

-Methode auf gewöhnliche

-Arrays angewendet wird, muss das Array

sortiert werden

Das obige ist der detaillierte Inhalt vonDetaillierte Erläuterung der Implementierungsmethode der Halbsuche in der JS-Array-Suche. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!