Algorithmen: Lineare Suche und binäre Suche

Es gibt einige einfache Algorithmen, die grundlegende Konzepte der Logik und Datenstruktur einführen, während andere auf eine größere Komplexität abzielen.

Suchalgorithmen sind nützlich, um Informationen in Datenmengen zu finden, beispielsweise um einen Kontakt in einem Telefonbuch oder eine Datei auf einem Computer zu finden.

In diesem Sinne soll dieser Artikel eine Einführung in die Konzepte der linearen Such- und binären Suchalgorithmen geben.

1. Lineare Suche

• Durchsuchen Sie eine Liste nacheinander, um ein Element zu finden
• Ein Beispiel wäre die Suche nach einer bestimmten Zahl in einem Array

Der Lineare Suchalgorithmus bedeutet in einer narrativen Aussage, dass es ein Array von Ganzzahlen und einen Wert gibt, der als Referenz für die Suche dient und als Ziel bezeichnet wird. Dabei handelt es sich um die Eingabeparameter. In diesem Sinne gibt es eine Funktion, die diese Werte empfängt und damit zunächst jede Position dieses Arrays bis zur maximalen Größe der vorhandenen Positionen durchläuft, wobei sie dafür zunächst ein for und dann mit einem if it verwendet Bedingt ist die Prüfung darauf, ob jede Position einen Wert hat, der dem Ziel entspricht. Wenn der Wert gefunden wird, gibt die Funktion den Index dieser Position zurück oder gibt -1 zurück, was für nicht gefundene Fälle steht.

Ein Beispiel für die Verwendung von JavaScript wäre:

function linearSearch(array, target) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === target) {
      return i; 
    }
  }
  return -1; 
}

Daher zielt dieser Algorithmus darauf ab, die Position oder den Index zurückzugeben, an der sich das Element befindet, oder er sucht sogar einfach das erste entsprechende Element, ohne dass nach dem Auffinden fortgefahren werden muss. Dieses Verhalten tritt aufgrund der Anweisungen des Algorithmus auf, der, wenn seine Bedingung erfüllt ist, die Rückgabe mit dem Elementindex ausführt und danach die Schleife verlässt und die Funktion beendet.

Dieser Algorithmus kann in Szenarien nützlich sein, in denen kleine oder ungeordnete Listen vorhanden sind. Jedes Element muss möglicherweise durchlaufen werden, und es gibt keinen zusätzlichen Speicherverbrauch.

2. Binäre Suche

• Scrollen Sie durch eine geordnete Liste, um ein Element zu finden
• Ein Beispiel wäre die Suche nach einer bestimmten Zahl in einem Array

Der Binärer Suchalgorithmus ist eine effizientere Form des Algorithmus zum Suchen eines bestimmten Werts in einem sortierten Array. Dies funktioniert durch wiederholtes Teilen des Suchbereichs in zwei Hälften, wodurch es deutlich schneller ist als die lineare Suche nach großen Datensätzen. Die binäre Suche hat eine O(log n)-Komplexität, während die lineare Suche eine O(n)-Komplexität hat.

Als Beispiel in JavaScript haben wir:

function linearSearch(array, target) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === target) {
      return i; 
    }
  }
  return -1; 
}

Die Logik besteht darin, mit zwei Zeigern zu beginnen, einer am Anfang (niedrig) und der andere am Ende (hoch) des Arrays. Somit wird der mittlere Index berechnet: const middle = Math.floor((low high) / 2). Dabei wird bei jedem Schritt das mittlere Element mit dem Ziel verglichen: Wenn das mittlere Element gleich dem Ziel ist, wird der Index zurückgegeben. Wenn jedoch das mittlere Element kleiner als das Ziel ist oder das mittlere < Ziel bedeutet, die kleinsten Zahlen zu verwerfen und den Anfang als niedrig = mittel 1 zu platzieren. Wenn das mittlere Element wiederum größer als die Zielmitte > Ziel, Zahlen, die größer als das Ziel sind, werden verworfen und der endgültige Index wird auf hoch = mittel – 1 angepasst. Dieser Vorgang wird wiederholt, bis das Ziel gefunden wird oder wenn der Bereich ungültig wird, im Fall von niedrig > hoch.

Die binäre Suche kann effizient sein, wenn geordnete Daten gefunden werden, beispielsweise in einem alphabetischen Wörterbuch oder einer Reihe geordneter Daten. Sie sind in der Regel schneller und effizienter, da das Problem in jeder Iteration in kleinere Teilprobleme unterteilt werden kann.

Daher versteht es sich, dass die lineare Suche einfach ist und bei kleinen Listen funktioniert. Die binäre Suche ist viel effizienter, erfordert jedoch geordnete Daten.

Das Verständnis der Funktionsweise verschiedener Algorithmen und ihrer Einsatzkontexte ist ein wichtiger Schritt auf dem Weg zur Entwicklung effizienter Computerlösungen. Versuchen Sie, diese Methoden zu implementieren und zu analysieren, und entdecken Sie, wie diese Strategien angepasst werden können, um reale Herausforderungen zu lösen. =)

Das obige ist der detaillierte Inhalt vonAlgorithmen: Lineare Suche und binäre Suche. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!