Quels sont les algorithmes de recherche de tableaux ?

Une collection d'algorithmes de recherche de tableau : recherche linéaire : parcours du tableau, complexité temporelle O(n). Recherche binaire (tableau ordonné uniquement) : divisez le tableau en deux, complexité temporelle O (log n). Table de hachage : recherche rapide à l'aide de la valeur clé, complexité temporelle O(1).

Liste complète des algorithmes de recherche de tableau

En informatique, les algorithmes de recherche de tableau sont utilisés pour trouver des éléments spécifiques dans un tableau ordonné ou non ordonné. Cet article explorera divers algorithmes de recherche de tableaux, y compris leur complexité temporelle et des exemples pratiques.

Recherche linéaire

Complexité temporelle : O(n)

La recherche linéaire est l'algorithme de recherche le plus simple et le plus direct. Il commence au début du tableau et compare les éléments un par un jusqu'à ce qu'il trouve l'élément cible ou atteigne la fin du tableau.

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

Recherche binaire

Complexité temporelle : O(log n)

La recherche binaire est utilisée pour rechercher dans un tableau ordonné. Il restreint la recherche en divisant à plusieurs reprises le tableau en deux.

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

Table de hachage

Complexité temporelle : O(1)

Une table de hachage est une structure de données qui nous permet de trouver rapidement des éléments par valeur clé. Les tableaux peuvent être utilisés comme structure de données sous-jacente pour les tables de hachage, où l'index est utilisé comme clé.

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

Exemple pratique

Considérons l'exemple de recherche par tableau suivant pour trouver les scores des élèves :

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

Si nous voulons trouver la partition de "Alice Johnson", nous pouvons utiliser la recherche linéaire :

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

Alternativement, si le tableau est trié par nom, nous pouvons utiliser la recherche binaire :

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!