How to implement and use the Binarysearch method?

Question

How to implement and use the method BinarySearch of a List<T>? I’m having difficulty implementing 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));
}

It returns only the index of an element in the list if it exists in the list? How could this method be used?

Answer 1

Exactly, it does a search on the values and returns the number of the element in the list. If it does not find it will return a negative number.

Note that it only works if the list values are sorted, you have to guarantee this on your own. If it is not sorted then any result can be returned and will not be a correct one, except by pure coincidence.

If the list is not sorted then the search has to be done sequentially (Find(), for example), which is almost guaranteed to be slower, possibly absurdly slower on large lists.

Can you guarantee that the list is classified? I doubt, this is highly unusual and if it is because it ranked earlier, which will be very inefficient.

If you want the structure to be guaranteed to be classified you have to use another one. For example, the SortedList or the SortedDictionary. In them a search for values works as binary search.

Obviously this method in this form in this code adds little. Of course it can have a purpose of creating an abstraction, if this is done consciously, ok.

Answer 2

First, to use this method it is necessary that the list is orderly. This is a precondition for the binary search algorithm, but it doesn’t hurt to remember...

Second, the method of BinarySearch with a single argument assumes that the list is ordered according to the "natural" comparison criterion of its elements. That is, it is necessary so much that these elements implement the interface IComparable (or its generic variant) if 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 comparison criteria, use the variant that receives a IComparer. Always remembering that the list needs to be ordered under the same criterion, for binary search to work properly.

The return of the method 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 can be returned, not necessarily the first one (depends on how many elements the list has and which positions its element occupies).

If the return is a negative number, the element is not in the list. If your goal is just to search, just test if the return is less than zero. But if you want insert this element in the list if it is no longer there, the return value can help you determine where this insertion should occur: just take the bit-by-bit add-on 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

Example in the ideone.