如何创建适用于数组中字符串的二进制搜索算法？

Question

我正在尝试对数组中的字符串进行二进制搜索，但似乎无法正常工作。这是我必须开始的。（这是针对数字的，但我在任何地方都找不到二进制字符串搜索的任何示例）。

        private void ButtonBinary_Click(object sender, EventArgs e)
        {
            int min = 0;
            int max = arraySize - 1;
            if (!(Int32.TryParse(TextBoxSearch.Text)))
            {
                TextBoxMessage.Text = "You must enter an integer";
                return;
            }
            while (min <= max)
            {
                int mid = (min + max) / 2;
                if (target == integerArray[mid])
                {
                    TextBoxMessage.Text = target + " Found at index " + mid + 
                        ".";
                    return;
                }
                else if (integerArray[mid] >= target)
                {
                    max = mid - 1;
                }
                else
                {
                    min = mid + 1;
                }
            }
            TextBoxMessage.Text = "Not Found, try again.";
        }

Answer 1

二分搜索的关键组成部分是您使用有序数据集进行搜索。它依赖于这样的概念，即如果（例如）x > myArray[10]，这本质上意味着 x 也大于 myArray[0] 到 myArray[9]。

二分查找的核心逻辑是这样的：

while (/*we are looking in a non-zero-length range*/)
{
    // find the middle point of the current range
    int mid = (min + max) / 2;

    if (/* match found */)
    {
        // search concluded, we found it!
    }
    else if (/* searched value is smaller than middle point */)
    {
        // do a search in the lower half of the range
    }
    else /* searched value is larger than middle */
    {
        // do a search in the upper half of the range
    }
}

// if we get here, and the search did not conclude, then it must not have existed

请注意此逻辑的 none 如何真正关心我们正在使用的数据类型。它唯一关心的是：

要搜索的值数组已排序
可以比较我们正在处理的值（即 a < b）

所以，如果你想使用字符串而不是整数，你所要做的就是：

确保你的数组是按字母顺序排列的

这个不太难：

string[] myOrderedArray = myUnorderedArray
                              .OrderBy(x => x)
                              .ToArray();

能够找出两个字符串的字母顺序（即"abc" < "bcd"）

如果您 google“C# 比较字符串”，您会很容易找到 String.Compare 方法，它正是这样做的。

var compareResult = String.Compare(myFirstString, mySecondString);

if(compareResult < 0)
    Console.WriteLine("Alphabetical order: myFirstString before mySecondString");
else if(compareResult > 0)
    Console.WriteLine("Alphabetical order: mySecondString before myFirstString");

请注意这与您当前的 if else 逻辑非常相似。

@DmitryBychenko I've been specifically asked to not use Binary.Search, : ( – LaggyAu

因为我怀疑这是作业，或者至少是专门为学习目的而给你的挑战，所以我有意选择不为你编写代码。我把将上述信息组合成工作代码作为练习留给你。

如何创建适用于数组中字符串的二进制搜索算法？

How do I create a binary search algorithm that works with strings in an array?

c#

search

binary-search