ArrayList BinarySearch

Question

Sono impegnato a prepararsi per l'esame MCTS 70-536, secondo il libro esame (Microsoft Press - .NET Framework - Application Development Foundation a ritmo corredo di addestramento 2a edizione), questo codice di esempio:

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

Invia il valore '2' alla console perché l'elemento 'questo' è all'indice 2. D'accordo è l'output che ottengo quando eseguo quel codice.

Tuttavia, se corro

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

mi aspetto di ottenere il valore 1 nella console dal 'mondo' sarebbe nella posizione di indice 1, ma ottengo il -7 valore?

Qualcuno potrebbe spiegare come funziona?

Grazie

Answer 1

L'array si sta eseguendo la ricerca binaria su non è ordinato. Questo è un requisito per il funzionamento di BinarySearch.

Essendo non ordinato, confonde l'algoritmo di ricerca e fa pensare che "mondo" dovrebbe essere al settimo posto, ma non è nell'array: il risultato è -7.

Answer 2

Tratto direttamente da MSDN documentazione di ArrayList.BinarySearch (http://msdn.microsoft.com/en-us/library/5tzt7yz3%28VS.85%29.aspx)

Il parametro valore e ciascun elemento del ArrayList deve implementare l'interfaccia IComparable , che viene utilizzato per confronti . Gli elementi della ArrayList devono già essere ordinati nel valore di incremento secondo l'ordine definito dall'implementazione di IComparable ; in caso contrario, il risultato potrebbe non essere corretto.

Answer 3

Dal documentation:

L'indice a base zero del valore nel filtrate ArrayList, se si pensa valore; altrimenti, un numero negativo, che è il complemento bitwise dell'indice di il successivo elemento che è maggiore valore o, se non v'è alcun elemento maggiore , il complemento bitwise di conte.

Avviso il ordinato parola.

Answer 4

Domanda già risposta ma aggiunta per riferimento.

BinarySearch trova gli elementi utilizzando un algoritmo ordinato. Nell'esempio l'ordinamento predefinito è alfabetico, quindi "mondo" dovrebbe essere l'ultimo, quindi il numero 7.

Verrà visualizzato un overloader di BinarySearch che accetta un oggetto IComparer. Per non fornire questo dà l'ordinamento predefinito alfabetico.

Ma se è stato implementato il metodo "reverseSort" come suggerisce il libro, è necessario passare la funzione BinarySearch all'oggetto "reverseSort".

In questo modo;

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

anche come l'ho trovato molto interessante se si implementa la classe "reverseSort" e fare una Console.WriteLine su cui valori ottenere confronto, i risultati non erano ciò che mi aspettavo. Ho passato un po 'di tempo a cercare di capire quale fosse l'algoritmo.