Quelles sont les méthodes de stockage et les exigences en matière de disposition des éléments pour les tables adaptées à la recherche binaire ?

Les exigences en matière de méthode de stockage et de disposition des éléments de la table adaptée à la recherche binaire sont : le stockage séquentiel et les éléments sont dans l'ordre. La recherche binaire est une méthode de recherche plus efficace, qui nécessite que le tableau linéaire adopte une structure de stockage séquentielle et que les éléments du tableau soient classés par mots-clés.

La recherche binaire est également appelée recherche binaire, qui est une méthode de recherche plus efficace. Cependant, la recherche binaire nécessite que le tableau linéaire adopte une structure de stockage séquentielle et que les éléments du tableau soient classés par mots-clés.

Tout d'abord, en supposant que les éléments du tableau sont classés par ordre croissant, comparez le mot-clé enregistré en position médiane du tableau avec le mot-clé de recherche Si les deux sont égaux, la recherche est réussie sinon, utilisez l'enregistrement de la position médiane pour diviser le tableau en premier. Pour les deux derniers sous-tableaux, si le mot-clé enregistré en position médiane est supérieur au mot-clé de recherche, la sous-table précédente sera recherchée plus en détail, sinon ce dernier sous -table sera recherché plus loin. Répétez le processus ci-dessus jusqu'à ce qu'un enregistrement répondant aux conditions soit trouvé, ce qui rend la recherche réussie, ou jusqu'à ce que la sous-table n'existe plus, auquel cas la recherche échoue.

Exigences de l'algorithme

1. Une structure de stockage séquentielle doit être utilisée.

2. Ils doivent être classés par taille de mot-clé.

Nombre de comparaisons

Formule de calcul :

Lorsque la table de séquence comporte n mots-clés :

Lorsque la recherche échoue, à au moins Comparez les mots-clés une fois ; lorsque la recherche est réussie, le nombre maximum de comparaisons de mots-clés est de b.

Remarque : a, b, n sont tous des entiers positifs.

Explication

La méthode de demi-recherche est également appelée méthode de recherche binaire. Elle utilise pleinement la relation d'ordre entre les éléments et adopte la méthode diviser pour régner. stratégie pour résoudre le problème dans le pire des cas. La tâche de recherche peut être complétée en O(log n). Son idée de base est la suivante : (en supposant que les éléments du tableau sont classés par ordre croissant) divisez n éléments en deux moitiés avec à peu près le même nombre, prenez a[n/2] et comparez-le avec le x que vous voulez trouver, si x= a[n/ 2] alors x est trouvé et l'algorithme se termine ; si x

Pour plus de connaissances connexes, veuillez visiter : Site Web PHP chinois !

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!