Que se passe-t-il si l'on tente une recherche binaire sur un ensemble de données non triées ?

Question

Que se passe-t-il si l'on tente une recherche binaire sur un ensemble de données non triées ?

Answer 1

Les résultats sont imprévisibles. Si l'ensemble de données contient la cible, celle-ci peut être trouvée ou non.

EDIT Juste pour le plaisir, j'ai fait une petite expérience. Tout d'abord, j'ai choisi une taille de tableau et généré un tableau d'int {0, 1, ..., taille-1}. Ensuite, j'ai mélangé le tableau, effectué une recherche binaire pour chaque valeur 0, 1, ..., taille-1 et compté combien de ces valeurs ont été trouvées. Pour chaque taille, j'ai répété les étapes de mélange et de recherche de chaque valeur 100 000 fois et j'ai enregistré le pourcentage de recherches réussies. (Les résultats sont les suivants (arrondis au pourcentage le plus proche) :)

Size    % Hit
 10      34%
 20      22%
 30      16%
 40      13%
 50      11%
 60      10%
 70       9%
 80       8%
 90       7%
100       6%

Par conséquent, plus le tableau est grand, plus les effets de l'absence de tri sont importants. Même pour des tableaux relativement petits, les résultats sont assez radicaux.

Answer 2

Il est presque certain que vous ne trouverez pas l'élément que vous recherchez. Si le tableau est la plupart du temps trié, vous pourriez avoir de la chance.

L'algorithme pourrait être mis en œuvre de manière à détecter cela avec une certaine probabilité, mais à moins d'effectuer un balayage complet du tableau, il n'y a aucun moyen de garantie qu'une recherche binaire détectera cette condition d'erreur.

Answer 3

La recherche binaire est destiné à travailler sur un Si elle est effectuée sur un tableau non trié, alors la fonction résultat sera certainement imprévisible et peu fiable .

Answer 4

La recherche binaire repose sur le tri des données. Elle choisit un élément dans un tableau et détermine 1. S'il s'agit de l'élément recherché 2. S'il ne s'agit pas de l'élément recherché, où peut-il trouver cet élément ?

Le deuxième point repose sur le tri des données pour prendre une décision. Imaginez des données non triées. En comparant la clé de recherche avec l'élément que nous avons sélectionné, nous ne serons pas en mesure d'identifier l'endroit où l'élément pourrait se trouver.

La recherche binaire ne peut donc pas fonctionner de manière cohérente avec des données non triées.