How to implement and use the BinarySearch method of a List<T> ? I'm having difficulty implementing it and also how to use it in a practical way.
Follow the example for illustration:
int BuscaBinaria(List<string> lista, string parametro)
{
return (lista.BinarySearch(parametro));
}
Does it return only the index of an element in the list if it exists in the list? How could this method be used?
First, to use this method, the list must be ordered . This is a precondition for the binary search algorithm, but it's easy to remember ...
Second, the BinarySearch method with a single argument assumes that the list is ordered according to the criterion of "natural" comparison of its elements. That is, it is necessary for these elements to implement the interface IComparable (or its generic variant) as long as the list is ordered according to this criterion. In the case of string lists, the comparison is given in lexicographic order.
If you need more control over the benchmark, use the variant that receives a IComparer . Always remember that the list must be ordered under the same criteria , so that the binary search works correctly.
The method return is the position the element is in the list, if it is there, or a negative number if it is not. Note that if there is more than one occurrence of the element in the list, any of them may be returned, not necessarily the first one (depending on how many elements the list has and what positions its element occupies).
If the return is a negative number, the element is not in the list. If your goal is to just fetch, just test if the return is less than zero. But if you want to insert this element in the list if it is not already there, the return value can help you determine where this insertion should occur: just pick up the bitwise complement of the return value:
List<string> lista = new List<string>() { "aoo", "bar", "baz" };
Console.WriteLine(lista.BinarySearch("bar")); // Está na lista (posição 1)
Console.WriteLine(lista.BinarySearch("bay")); // Não na lista (negativo)
Console.WriteLine(~lista.BinarySearch("bay")); // Se for inserir, insira na posição 2
Exactly, it does a search on the values and returns the number of the element in the list. If it does not find it it will return a negative number.
Note that this only works if the values in the list are sorted. You have to secure this on your own. If it is not any result can be returned and probably will not be correct.
If the list is not sorted, then the search will have to be done sequentially ( Find() ", for example), which is almost guaranteed to be slower, possibly absurdly slower on larger lists.
If you want the structure to be classified, you have to use another one. For example, SortedList or SortedDictionary . In them, a search for values works as a binary search.
Obviously this method in this form, in this code adds little. Of course, it may have a purpose to create an abstraction, if this is done consciously, ok.