java - 二进制搜索中的索引越界异常

Question

我对发生这种情况的确切位置感到困惑。我已经在纸上追踪了这个简单的代码并使用了计算机，但我无法弄清楚。在我的示例中，我创建了一个 {1, 2, 3, 4, 5} 数组，它对数字 4 和 5 产生了这个错误。它对数字 1、2 和 3 以及不在数组。有人可以帮忙吗？

public static int search(int[] ar, int num)
{
    int low=0;
    int hi=ar.length-1;
    int mid=(low+hi/2);
    while(hi>=low || mid<=low || mid>=hi )
    {
        if(ar[mid]==num)
        {
            return mid;
        }
        else if(ar[mid]>num)
        {
            hi=mid-1;
            mid=(low+hi/2);
        }
        else
        {
            low=mid+1;
            mid=(low+hi/2);
        }
    }
    return -1;
}

Answer 1

mid=(low+hi/2);

您需要使用 prantheses 以便在添加低和高之后进行划分。

mid=(low+hi) / 2;

此外，您的循环条件不应允许 mid >high，因为这样它就不会因不在数组中的大量数字而终止。

Answer 2

问题是您继续循环的条件。尝试改变这个：

while (hi>=low || mid<=low || mid>=hi) {

对此：

while (hi>=low) {

如果hi < low，您不希望继续循环而不管其他两个条件（我认为，其中一个条件永远为真，如果hi < low）。