Общий бинарный поиск в C #

Question

Ниже приведен мой общий бинарный поиск.Он работает нормально с массивом целочисленных типов (он находит все элементы в нем).Но проблема возникает, когда я использую строковый массив, чтобы найти любые строковые данные.Он работает нормально для первого и последнего индексных элементов, но я не могу найти средние элементы.

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

Бинарный поиск требует сортировки ввода .Как сортируется «b, a, ab, abc, c»?Похоже, он не сортируется по какому-либо очевидному ключу сортировки.Если вы пытаетесь искать несортированные данные, вам следует использовать хэш-набор, а не двоичный поиск в списке.

Кроме того, ваше вычисление средней точки немного ошибочно, поскольку добавление high + low может переполнить.Затем он становится отрицательным числом, которое делится на два.

Это крайне маловероятно для массивов реалистичного размера, но вполне возможно, что вы когда-нибудь захотите использовать этот алгоритм для типов данных, которые поддерживают индексирование с помощьюбольшие целые числа, такие как отображенный в памяти файл отсортированных данных.

Лучшей практикой для написания алгоритма бинарного поиска является (high - low) / 2 + low при вычислении средней точки, потому что она остается в диапазоне все время.

Answer 2

// Бинарный поиск рекурсивный метод

    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);

Answer 3

pst Ваш совет действительно сработал. :) этот код работает как для int, так и для строки.

    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

Подозреваемые две строки:

high = mid + 1
low = mid + 1

Хмм.Посмотрите на смещения.Конечно, это хорошо задокументировано Алгоритм двоичного поиска в Википедии.Вы также делаете дополнительную работу.Изучите псевдокод и примеры внимательно.