通用二进制在C＃中搜索 [英] Generic Binary Search in C#

问题描述

下面是我的通用二进制搜索。它的工作原理没关系的整数类型的数组（它找到的所有元素在里面）。但是，当我使用一个字符串数组来找到任何字符串数据的问题就出现了。它运行好了第一个索引和最后一个索引元素，但我无法找到中间的元素。

 字符串数组=新的String [] {B，A，AB，ABC，C};

公共静态无效的二分查找＆LT; T＆GT;（T []数组，T searchFor，的Comparer＆LT; T＆GT;比较器）{

        INT高，低，中，
        高= array.Length  -  1;
        低= 0;
        如果（数组[0] .Equals（searchFor））
            Console.WriteLine（值{0}发现了在指数{1}，数组[0]，0）;
        否则，如果（阵列[大] .Equals（searchFor））
            Console.WriteLine（值{0}发现了在指数{1}，数组[高]，高）;
        其他
        {
            而（低＆LT; =高）
            {
                中期=（高+低）/ 2;
                如果（comparer.Compare（数组[MID]，searchFor）== 0）
                {
                    Console.WriteLine（值{0}发现了在指数{1}，数组[MID]，中）;
                    打破;
                }
                其他
                {
                    如果（comparer.Compare（searchFor，数组[MID]）大于0）
                        高=中等+ 1;
                    其他
                        低=中等+ 1;
                }

            }
            如果（低＆GT;高）
            {
                Console.WriteLine（值未找到集）;
            }
        }
    }
 

解决方案

一个二进制搜索要求输入进行排序。如何为B，A，AB，ABC，C排序？它似乎并没有被排序在任何明显的排序键。如果您正在查找未排序的数据，你应该使用哈希集合，而不是一个列表中的二进制搜索。

另外，你的计算中点的是巧妙地错误的，因为增加了高+低可能会溢出。然后，它变成一个负数，这是由两个分开的

这是极不可能为现实大小的数组，但它是完全可能的，你要哪天用这个算法，支持索引与大的整数，如排序的数据的内存映射文件的数据类型。

写二进制搜索算法，最好的做法是做（高 - 低）/ 2 +低计算中点时，因为停留在范围内的全部时间

Below is my Generic Binary Search. It works okay with the integers type array (it finds all the elements in it). But the problem arises when I use a string array to find any string data. It runs okay for the first index and last index elements but I can't find the middle elements.

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

解决方案

A binary search requires that the input be sorted. How is "b, a, ab, abc, c" sorted? It does not appear to be sorted on any obvious sort key. If you are trying to search unsorted data you should be using a hash set, not a binary search on a list.

Also, your calculation of midpoint is subtly wrong because the addition of high + low can overflow. It then becomes a negative number, which is divided by two.

This is extremely unlikely for realistically-sized arrays but it is entirely possible that you'll want to use this algorithm someday for data types that support indexing with large integers, like a memory-mapped file of sorted data.

The best practice for writing a binary search algorithm is to do (high - low) / 2 + low when calculating the midpoint, because that stays in range the whole time.

这篇关于通用二进制在C＃中搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！