Maison > Problème commun > 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 ?

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 ?

青灯夜游
Libérer: 2020-08-31 15:27:47
original
14559 Les gens l'ont consulté

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.

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 ?

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!

Étiquettes associées:
source:php.cn
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal