Welche Suchalgorithmen gibt es für Arrays?

Eine Sammlung von Array-Suchalgorithmen: lineare Suche: Durchlaufen des Arrays, zeitliche Komplexität O(n). Binäre Suche (nur geordnetes Array): Teilen Sie das Array in zwei, zeitliche Komplexität O(log n). Hash-Tabelle: Schnelle Suche mit Schlüsselwert, Zeitkomplexität O(1).

Umfassende Liste von Array-Suchalgorithmen

In der Informatik werden Array-Suchalgorithmen verwendet, um bestimmte Elemente in einem geordneten oder ungeordneten Array zu finden. In diesem Artikel werden verschiedene Array-Suchalgorithmen untersucht, einschließlich ihrer zeitlichen Komplexität und praktischer Beispiele.

Lineare Suche

Zeitliche Komplexität: O(n)

Die lineare Suche ist der einfachste und direkteste Suchalgorithmus. Es beginnt am Anfang des Arrays und vergleicht die Elemente nacheinander, bis das Zielelement gefunden oder das Ende des Arrays erreicht wird.

def linear_search(arr, target):
  for i in range(len(arr)):
    if arr[i] == target:
      return i
  return -1

Binäre Suche

Zeitliche Komplexität: O(log n)

Die binäre Suche wird verwendet, um in einem geordneten Array zu suchen. Es schränkt die Suche ein, indem das Array wiederholt in zwei Hälften geteilt wird.

def binary_search(arr, target):
  left, right = 0, len(arr) - 1
  while left <= right:
    mid = (left + right) // 2
    if arr[mid] == target:
      return mid
    elif arr[mid] < target:
      left = mid + 1
    else:
      right = mid - 1
  return -1

Hash-Tabelle

Zeitliche Komplexität: O(1)

Eine Hash-Tabelle ist eine Datenstruktur, die es uns ermöglicht, Elemente schnell anhand des Schlüsselwerts zu finden. Arrays können als zugrunde liegende Datenstruktur für Hash-Tabellen verwendet werden, wobei der Index als Schlüssel verwendet wird.

def hash_search(arr, target):
  hash_table = {}
  for i in range(len(arr)):
    hash_table[arr[i]] = i
  if target in hash_table:
    return hash_table[target]
  else:
    return -1

Praktisches Beispiel

Betrachten Sie das folgende Array-Suchbeispiel, um Schülernoten zu finden:

students = [
  {'name': 'John Doe', 'score': 85},
  {'name': 'Jane Doe', 'score': 90},
  {'name': 'Bill Smith', 'score': 75},
  {'name': 'Alice Johnson', 'score': 95}
]

Wenn wir die Punktzahl von „Alice Johnson“ finden möchten, können wir die lineare Suche verwenden:

for student in students:
  if student['name'] == 'Alice Johnson':
    print(student['score'])  # 输出：95

Alternativ, wenn das Array sortiert ist Nach Namen können wir die binäre Suche verwenden:

students.sort(key=lambda x: x['name'])

left, right = 0, len(students) - 1
while left <= right:
  mid = (left + right) // 2
  if students[mid]['name'] == 'Alice Johnson':
    print(students[mid]['score'])  # 输出：95
    break
  elif students[mid]['name'] < 'Alice Johnson':
    left = mid + 1
  else:
    right = mid - 1

Das obige ist der detaillierte Inhalt vonWelche Suchalgorithmen gibt es für Arrays?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!