c# - 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，因为它始终保持在范围内。