Búsqueda binaria genérica en C#

Question

A continuación se encuentra mi Búsqueda binaria genérica. Funciona bien con la matriz de tipos enteros (encuentra todos los elementos en ella). Pero el problema surge cuando uso una matriz de cadenas para encontrar cualquier dato de cadena. Corre bien para el primer índice y los últimos elementos del índice, pero no puedo encontrar los elementos del medio.

Stringarray = new string[] { "b", "a", "ab", "abc", "c" }; 

public static void BinarySearch<T>(T[] array, T searchFor, Comparer<T> comparer) { 

     int high, low, mid; 
     high = array.Length - 1; 
     low = 0; 
     if (array[0].Equals(searchFor))    
      Console.WriteLine("Value {0} Found At Index {1}",array[0],0); 
     else if (array[high].Equals(searchFor)) 
      Console.WriteLine("Value {0} Found At Index {1}", array[high], high); 
     else 
     { 
      while (low <= high) 
      { 
       mid = (high + low)/2; 
       if (comparer.Compare(array[mid], searchFor) == 0) 
       { 
        Console.WriteLine("Value {0} Found At Index {1}", array[mid], mid); 
        break; 
       } 
       else 
       { 
        if (comparer.Compare(searchFor, array[mid]) > 0) 
         high = mid + 1; 
        else 
         low = mid + 1; 
       } 

      } 
      if (low > high) 
      { 
       Console.WriteLine("Value Not Found In the Collection"); 
      } 
     }     
    } 

Answer 1

Las dos líneas son sospechosos:

high = mid + 1 
low = mid + 1 

Hmm. Mire las compensaciones. Por supuesto, esto está bien documentado Binary Search Algorithm en Wikipedia. También haces trabajo extra. Examine el pseudo-código y los ejemplos de cerca.

Answer 2

Una búsqueda binaria requiere que la entrada se ordene. ¿Cómo se clasifica "b, a, ab, abc, c"? No parece estar ordenado en ninguna clave de clasificación obvia. Si intenta buscar datos sin ordenar, debe usar un conjunto de hash, no una búsqueda binaria en una lista.

Además, su cálculo del punto medio es sutilmente incorrecto porque la adición de alto + bajo puede desbordarse. Luego se convierte en un número negativo, que está dividido por dos.

Esto es extremadamente improbable para matrices de tamaño realista, pero es muy posible que desee utilizar este algoritmo algún día para tipos de datos que admitan la indexación con enteros grandes, como un archivo mapeado en memoria de datos ordenados.

La mejor práctica para escribir un algoritmo de búsqueda binaria es hacer (high - low)/2 + low al calcular el punto medio, ya que permanece dentro del rango todo el tiempo.

Answer 3

pst Su consejo realmente funcionó. :) este código funciona para int y string.

public static int BinarySearch<T>(T[] array, T searchFor, Comparer<T> comparer) 
    { 
     int high, low, mid; 
     high = array.Length - 1; 
     low = 0; 
     if (array[0].Equals(searchFor)) 
      return 0; 
     else if (array[high].Equals(searchFor)) 
      return high; 
     else 
     { 
      while (low <= high) 
      {     
       mid = (high + low)/2; 
       if (comparer.Compare(array[mid], searchFor) == 0)     
        return mid;      
       else if (comparer.Compare(array[mid], searchFor) > 0)      
        high = mid - 1;      
       else      
        low = mid + 1;     
      } 
      return -1;     
     }     
    } 

Answer 4

// La búsqueda binaria método recursivo

public void BinarySearch(int[] input,int key,int start,int end) 
    { 
     int index=-1; 
     int mid=(start+end)/2; 
     if (input[start] <= key && key <= input[end]) 
     { 
      if (key < input[mid]) 
       BinarySearch(input, key, start, mid); 
      else if (key > input[mid]) 
       BinarySearch(input, key, mid + 1, end); 
      else if (key == input[mid]) 
       index = mid; 
      if (index != -1) 
       Console.WriteLine("got it at " + index); 
     } 
    } 

    int[] input4 = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; 
    BinarySearch(input4, 1, 0, 8);