使用字符串进行二分查找

Question

我有一个对象数组，我想使用二进制搜索来搜索日期/日期属性（用户决定）。

**编辑：我从文本文件中读取了 SharesArray[mid].Date 值（和日期值），示例为：05/02/2015、14/10/2014.The searchString 值将从用户那里获得，但格式与日期值相同。 **

这是我的第一次尝试，所以我只是尝试日期属性:

int high, low, mid;
high = SharesArray.Length - 1;
low = 0;

while (low <= high)
{
    mid = (low + high) / 2;
    if (String.Compare(SharesArray[mid].Date, searchString, true) == 0)
    {
        break;
    }
    else if (String.Compare(SharesArray[mid].Date, searchString, true) > 0)
    {
        high = mid - 1;
    }
    else if (String.Compare(SharesArray[mid].Date, searchString, true) < 0)
    {
        low = mid + 1;
    }

我也试过最后一个 else if 语句，就像 else 一样，这没有任何区别。

此外，String.Compare 部分中的 string1 和 string2 的排列是否重要？

Answer 1

你考虑过 LINQ 吗？

var searchIndex = SharesArray
    .Select(s => s.Date)
    .ToList()
    .BinarySearch(searchString);

Answer 2

在问题的评论中总结问答中的答案，以及一些额外的上下文。

对于二进制搜索，您需要注意一些要素

二进制搜索函数的输入数组必须排序。
鉴于您实现的算法，它们必须按升序排序。
你必须有一个三向比较函数，对于 compare(lhs, rhs) returns: < 0 if lhs < rhs, > 0 if lhs > rhs 和 0 如果 lhs == rhs.
compare 函数中参数的顺序很重要，如果你切换它们，你将走错分支并更改搜索上限而不是下限，反之亦然。
对于您的实施，您的顺序是正确的，lhs : SharesArray[mid].Date 和 rhs = searchString.
因为要比较日期，所以需要使用 DateTime.Compare 函数，并使用 DateTime.ParseExact(myString, "dd/MM/yyyy", CultureInfo.InvariantCulture); 将日期字符串转换为 DateTime 个实例。通过字符串比较，您会得到错误的结果，例如 "05/02/2015" < "14/10/2014".

然后还有一则趣闻（见here）：

枢轴值mid的计算容易出现整数溢出。如果您将其计算为

mid = (low + high) / 2;

然后 low + high 可能会变得大于整数。

因此，计算 mid 的首选方法是

`mid = low + ((high - low) >> 1);`.

使用字符串进行二分查找

Binary Search with Strings

c#

binary-search