El método List<T>.BinarySearch() utiliza un algoritmo de búsqueda binaria para ubicar un elemento específico en la Lista<T> ordenada o una parte de ella. Hay 3 métodos en la lista de sobrecarga de este método de la siguiente manera:
- Búsqueda binaria (T)
- Búsqueda binaria(T, IComparer<T>)
- Búsqueda binaria (Int32, Int32, T, IComparer<T>)
Método de búsqueda binaria (T)
Este método busca un elemento en toda la List<T> ordenada mediante el comparador predeterminado y devuelve el índice de base cero del elemento buscado.
Sintaxis:
public int BinarySearch (T item);
Aquí, el elemento es el objeto que se va a ubicar y el valor del elemento puede ser nulo o de tipo de referencia .
Tipo de devolución: si se encuentra el elemento , este método devuelve el índice basado en cero del elemento que se busca y, si no se encuentra, se devolverá un número negativo que es el complemento bit a bit del índice del siguiente elemento y el complemento es mayor que ese artículo. Si no hay un elemento más grande, se devolverá el complemento bit a bit de Count .
Excepción: este método dará InvalidOperationException si el comparador predeterminado Default no puede encontrar una implementación de la interfaz genérica IComparable<T> o la interfaz IComparable para el tipo T.
Los siguientes programas ilustran el uso del método mencionado anteriormente:
Ejemplo 1:
C#
// C# program to illustrate the
// List<T>.BinarySearch(T) Method
using System;
using System.Collections.Generic;
class GFG {
// Main Method
public static void Main()
{
// List creation
List<string> Geek = new List<string>();
// List elements
Geek.Add("ABCD");
Geek.Add("QRST");
Geek.Add("XYZ");
Geek.Add("IJKL");
Console.WriteLine("The Original List is:");
foreach(string g in Geek)
{
// prints original List
Console.WriteLine(g);
}
Console.WriteLine("\nThe List in Sorted form");
// sort the List
Geek.Sort();
Console.WriteLine();
foreach(string g in Geek)
{
// prints the sorted List
Console.WriteLine(g);
}
Console.WriteLine("\nInsert EFGH :");
// insert "EFGH" in the List
//"EFGH" insert into its original
// position when the List is sorted
int index = Geek.BinarySearch("EFGH");
if (index < 0)
{
Geek.Insert(~index, "EFGH");
}
Console.WriteLine();
foreach(string g in Geek)
{
// prints the sorted list
// after inserting "EFGH"
Console.WriteLine(g);
}
}
}
The Original List is: ABCD QRST XYZ IJKL The List in Sorted form ABCD IJKL QRST XYZ Insert EFGH : ABCD EFGH IJKL QRST XYZ
Ejemplo 2: En este ejemplo, la Lista se crea con algunos valores enteros y para insertar un nuevo entero usando el método BinarySearch(T) en la Lista usando una función definida por el usuario.
C#
// C# program to illustrate the
// List<T>.BinarySearch(T) Method
using System;
using System.Collections.Generic;
class GFG {
// method for inserting "3"
public void binarySearch(List<int> Geek)
{
// insert "3" in the List
Console.WriteLine("\nInsert 3 :");
// "3" insert into its original
// position when the List is
// sorted
int index = Geek.BinarySearch(3);
if (index < 0)
{
Geek.Insert(~index, 3);
}
foreach(int g in Geek)
{
// prints the sorted list
// after inserting "3"
Console.WriteLine(g);
}
}
}
// Driver Class
public class search {
public static void Main()
{
// List creation
GFG gg = new GFG();
List<int> Geek = new List<int>() {
5, 6, 1, 9};
Console.WriteLine("Original List");
foreach(int g in Geek)
{
Console.WriteLine(g);
// prints original List
}
Console.WriteLine("\nList in Sorted form");
Geek.Sort();
foreach(int g in Geek)
{
Console.WriteLine(g);
// prints the sorted List
}
// calling the method "binarySearch"
gg.binarySearch(Geek);
}
}
Original List 5 6 1 9 List in Sorted form 1 5 6 9 Insert 3 : 1 3 5 6 9
Método de búsqueda binaria (T)
Este método busca un elemento en toda la lista ordenada utilizando el comparador especificado y devuelve el índice de base cero del elemento buscado.
Sintaxis:
public int BinarySearch (elemento T, comparador System.Collections.Generic.IComparer<T>);
Parámetros:
- item : Es el elemento a ubicar y el valor del elemento puede ser nulo para los tipos de referencia.
- comparer : es la implementación de IComparer<T> para usar al comparar elementos.
Valor devuelto: si el elemento se encuentra, este método devuelve el índice basado en cero del elemento que se busca y, si no se encuentra, un número negativo que es el complemento bit a bit del índice del siguiente elemento que es más grande que el elemento. o, si no hay un elemento más grande, el complemento bit a bit de Count.
Excepción: este método dará InvalidOperationException si el comparador es nulo y el comparador predeterminado Default no puede encontrar una implementación de la interfaz genérica IComparable<T> o la interfaz IComparable para el tipo T .
Los siguientes programas ilustran el uso del método mencionado anteriormente:
Ejemplo 1:
C#
// C# program to demonstrate the
// List<T>.BinarySearch(T,
// IComparer<T>) Method
using System;
using System.Collections.Generic;
class GFG : IComparer<string> {
public int Compare(string x, string y)
{
if (x == null || y == null)
{
return 0;
}
return x.CompareTo(y);
//"CompareTo()" method
}
}
// Driver Class
class geek {
// Main Method
public static void Main()
{
// list creation
List<string> list1 = new List<string>();
// list elements
list1.Add("B");
list1.Add("C");
list1.Add("E");
list1.Add("A");
// prints Original list
Console.WriteLine("Original string");
foreach(string g in list1)
{
Console.WriteLine(g);
}
GFG gg = new GFG();
// sort the list
list1.Sort(gg);
// prints the sorted form of original list
Console.WriteLine("\nList in sorted form");
foreach(string g in list1)
{
Console.WriteLine(g);
}
//"D" is going to insert
//"gg" is the IComparer
int index = list1.BinarySearch("D", gg);
if (index < 0)
{
list1.Insert(~index, "D");
}
// prints the final List
Console.WriteLine("\nAfter inserting \"D\" in the List");
foreach(string g in list1)
{
Console.WriteLine(g);
}
}
}
Producción:
Original string B C E A List in sorted form A B C E After inserting "D" in the List A B C D E
Ejemplo 2: En este ejemplo, la Lista se crea con algunos valores enteros y para insertar un nuevo entero usando el método BinarySearch(T, Comparer <T>) en la Lista usando una función definida por el usuario.
C#
// C# program to demonstrate the
// List<T>.BinarySearch(T,
// IComparer<T>) Method
using System;
using System.Collections.Generic;
class GFG : IComparer<int> {
public int Compare(int x, int y)
{
if (x == 0 || y == 0)
{
return 0;
}
return x.CompareTo(y);
}
}
// Driver Class
class geek {
// Main Method
public static void Main()
{
// list creation
List<int> list1 = new List<int>() {
5, 6, 1, 9};
// prints Original list
Console.WriteLine("Original string");
foreach(int g in list1)
{
Console.WriteLine(g);
}
// creating object of class GFG
GFG gg = new GFG();
// sort the list
list1.Sort(gg);
// prints the sorted form
// of original list
Console.WriteLine("\nList in sorted form");
foreach(int g in list1)
{
Console.WriteLine(g);
}
bSearch b = new bSearch();
b.binarySearch(list1);
}
}
class bSearch {
public void binarySearch(List<int> list1)
{
// creating object of class GFG
GFG gg = new GFG();
// "3" is going to insert
// "gg" is the IComparer
int index = list1.BinarySearch(3, gg);
if (index < 0)
{
list1.Insert(~index, 3);
}
// prints the final List
Console.WriteLine("\nAfter inserting \"3\" in the List");
foreach(int g in list1)
{
Console.WriteLine(g);
}
}
}
Original string 5 6 1 9 List in sorted form 1 5 6 9 After inserting "3" in the List 1 3 5 6 9
Búsqueda binaria (Int32, Int32, T, IComparer<T>)
Este método se usa para buscar un rango de elementos en la List<T> ordenada para un elemento usando el comparador especificado y devuelve el índice de base cero del elemento.
Sintaxis:
public int BinarySearch (int index, int count, T item, System.Collections.Generic.IComparer<T> comparador);
Parámetros:
index : Es el índice inicial de base cero del rango a buscar.
count : Es la longitud del rango a buscar.
item : Es el objeto a localizar. El valor puede ser nulo para el tipo de referencia.
comparer : es la implementación de IComparer para usar al comparar elementos, o null para usar el comparador predeterminado Default.
Valor devuelto: Devuelve el índice de base cero del elemento en la lista ordenada <T>, si se encuentra el elemento; de lo contrario, un número negativo que es el complemento bit a bit del índice del siguiente elemento que es mayor que item o, si no hay ningún elemento mayor, el complemento bit a bit de Count.
Excepciones:
- ArgumentOutOfRangeException : si el índice es menor que 0 o el recuento es menor que 0.
- ArgumentException : si el índice y el recuento no representan un rango válido.
- InvalidOperationException : si el comparador es nulo.
Ejemplo:
C#
// C# program to demonstrate the
// List<T>.BinarySearch(Int32,
// Int32, T, Comparer <T>) method
using System;
using System.Collections.Generic;
class GFG : IComparer<int>
{
public int Compare(int x, int y)
{
if (x == 0 || y == 0)
{
return 0;
}
return x.CompareTo(y);
}
}
class search {
// "binarySearch" function
public void binarySearch(List<int> list1,
int i)
{
Console.WriteLine("\nBinarySearch a "+
"range and Insert 3");
// "gg" is the object of class GFG
GFG gg = new GFG();
// binary search
int index = list1.BinarySearch(0, i,
3, gg);
if (index < 0)
{
// insert "3"
list1.Insert(~index, 3);
i++;
}
Display(list1);
}
// "Display" function
public void Display(List<int> list)
{
foreach( int g in list )
{
Console.WriteLine(g);
}
}
}
// Driver Class
class geek
{
// Main Method
public static void Main()
{
List<int> list1 = new List<int>()
{
// list elements
15,4,2,9,5,7,6,8,10
};
int i = 7;
Console.WriteLine("Original List");
// "d" is the object of
// the class "search"
search d = new search();
// prints Original list
d.Display(list1);
// "gg" is the object
// of class GFG
GFG gg = new GFG();
Console.WriteLine("\nSort a range with "+
"the alternate comparer");
// sort is happens between
// index 1 to 7
list1.Sort(1, i, gg);
// prints sorted list
d.Display(list1);
// call "binarySearch" function
d.binarySearch(list1,i);
}
}
Original List 15 4 2 9 5 7 6 8 10 Sort a range with the alternate comparer 15 2 4 5 6 7 8 9 10 BinarySearch a range and Insert 3 15 2 3 4 5 6 7 8 9 10
Nota:
- Si List<T> contiene más de un elemento con el mismo valor, el método devuelve solo una de las apariciones y podría devolver cualquiera de las apariciones, no necesariamente la primera.
- List<T> ya debe estar ordenado de acuerdo con la implementación del comparador; de lo contrario, el resultado es incorrecto.
- Este método es una operación O(log n), donde n es el número de elementos en el rango.
Referencia:
Publicación traducida automáticamente
Artículo escrito por SoumikMondal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA