Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.0k views
in Technique[技术] by (71.8m points)

algorithm - Generic Binary Search in C#

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");
            }
        }                 
    }
See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

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.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...