c# - 排序数组的二分查找

Question

我正在尝试使用此二进制搜索代码搜索降序排序的数组。但是，在我对它进行排序并尝试搜索之后，它并没有返回任何结果，只是一个永远不会消失的加载图标，就好像它有一个无限循环一样。我不确定问题出在哪里，因为代码看起来合乎逻辑。

这是4.0框架的aspx，c#。提前致谢!

    protected void Button2_Click(object sender, EventArgs e)
    {
        String item = TextBox1.Text;
        int target = Convert.ToInt16(item);
        int mid, first = 0, last = mynumbers.Length - 1;

        //for a sorted array with descending values
        while (first<=last)
        {
            mid = (first + last) / 2;
            if (target < mynumbers[mid])
                first = mid + 1;
            if (target > mynumbers[mid])
                last = mid - 1;
            else
                Label11.Text = "Target " + item + " was found at index " + mynumbers[mid];

        }

Answer 1

Array类中有二分查找:

int index = Array.BinarySearch(mynumbers, target);

对于降序，这可以通过 ReverseComparer 轻松实现，它很容易写成:

    public class ReverseComparer<T> : IComparer<T>
    {
        public int Compare(T x, T y)
        {
            return Comparer<T>.Default.Compare(y, x);
        }
    }

然后:

int index = Array.BinarySearch(numbers, 7, new ReverseComparer<int>());

如果这是一项学术练习并且您必须使用自定义搜索，那么这当然不适用。如果它必须是类的自定义算法，那么问题是您必须在找到时跳出循环，并且索引位于 mid，而不是 mynumbers[mid] :

    //for a sorted array with descending values
    while (first<=last)
    {
        mid = (first + last) / 2;

        if (target < mynumbers[mid])
        {
            first = mid + 1;
        }

        if (target > mynumbers[mid])
        {
            last = mid - 1;
        }

        else
        {
            // the index is mid, not mynumbers[mid], and you need to break here
            // once found or it's an infinite loop once it finds it.
            Label11.Text = "Target " + item + " was found at index " + mid;
            break;
        }
    }

实际上，我可能会设置一个 bool 标志，而不是保持算法的纯净，而不是将查找与输出问题混在一起，这也会让您更容易判断如果您在未找到的情况下退出循环会发生什么:

    bool found = false;

    //for a sorted array with descending values
    while (!found && first<=last)
    {
        mid = (first + last) / 2;

        if (target < mynumbers[mid])
        {
            first = mid + 1;
        }

        if (target > mynumbers[mid])
        {
            last = mid - 1;
        }

        else
        {
            // You need to stop here once found or it's an infinite loop once it finds it.
            found = true;
        }
    }

    Label11.Text = found 
        ? "Item " + item + " was found at position " + mid
        : "Item " + item + " was not found";