ArrayList BinarySearch

Question

Je suis en train de préparer pour l'examen MCTS 70-536, selon le livre d'examen (Microsoft Press - .NET Framework - Développement d'applications Fondation Self Paced Training Kit 2e édition), cet exemple de code:

ArrayList al = new ArrayList(); 
al.AddRange(new string[] { "Hello", "world", "this", "is", "a", "test" }); 
Console.WriteLine(al.BinarySearch("this")); 

Envoie la valeur '2' à la console car l'élément 'this' est à l'index 2. D'accord, c'est la sortie que j'obtiens quand j'exécute ce code.

Cependant, si je lance

Console.WriteLine(al.BinarySearch("world")); 

Je vous attendre à obtenir la valeur 1 dans la console depuis « monde » serait à l'index 1, mais je reçois la -7 valeur?

Quelqu'un pourrait-il expliquer comment cela fonctionne?

Merci

Answer 1

Le tableau que vous effectuez la recherche binaire sur ne sont pas triés. Ceci est une condition pour que BinarySearch fonctionne. Etre non trié, confond l'algorithme de recherche, et fait penser que "monde" devrait être sur la 7ème place, mais il n'est pas dans le tableau: le résultat est -7.

Answer 2

prises directement à partir de la documentation MSDN ArrayList.BinarySearch (http://msdn.microsoft.com/en-us/library/5tzt7yz3%28VS.85%29.aspx)

Le paramètre de valeur et chaque élément de la liste de tableaux doit implémenter l'interface IComparable , qui est utilisé pour les comparaisons . Les éléments de l'ArrayList doivent déjà être triés en valeur croissante selon le tri ordre défini par l'implémentation IComparable ; sinon, le résultat peut être incorrect.

Answer 3

De l'documentation:

L'indice de base zéro de la valeur dans la liste de tableaux triés, si la valeur est trouvée; autrement, un nombre négatif, ce qui est le complément au niveau du bit de l'indice de l'élément suivant qui est plus grande que la valeur ou, s'il n'y a pas d'élément plus grand, le complément au niveau du bit de Count.

Notez le trié mot.

Answer 4

Une question a déjà été répondue mais a été ajoutée à titre de référence.

BinarySearch trouvera les éléments en utilisant un algorithme trié. Dans votre exemple, le tri par défaut est alphabétique, donc "world" doit être le dernier, d'où le numéro 7.

Vous verrez un overloader de BinarySearch qui accepte un objet IComparer. Pour ne pas fournir cela donne le type par défaut de l'alphabétique.Mais si vous avez implémenté la méthode "reverseSort" comme le suggère le livre, vous devrez passer la fonction BinarySearch à l'objet "reverseSort".

Comme ceci;

Console.WriteLine(al.BinarySearch(al, new reverseSort())); 

tout aussi je l'ai trouvé très intéressant si vous implémentez la classe « reverseSort » et faire une Console.WriteLine sur quelles valeurs se compare, les résultats ne sont pas ce que j'espérais. J'ai passé un peu de temps à essayer de comprendre quel était l'algorithme.