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"是如何排序的？它似乎没有按任何明显的排序键排序.如果您尝试搜索未排序的数据,则应使用哈希集,而不是列表上的二进制搜索.

此外,您对中点的计算是巧妙的错误,因为加上高+低可能会溢出.然后它变成负数,除以2.

对于真实大小的数组来说,这是极不可能的,但完全有可能你有一天会想要使用这个算法来支持使用大整数进行索引的数据类型,比如排序数据的内存映射文件.

编写二进制搜索算法的最佳实践是(high - low) / 2 + low在计算中点时执行,因为它始终保持在范围内.

Answer 2

这两行是可疑的：

high = mid + 1
low = mid + 1

唔。查看偏移量。当然，维基百科上有详细记录的二分搜索算法。你还做额外的工作。仔细检查伪代码和示例。