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);

您需要使用补语，以便在添加 low 和 hi 后进行除法。

mid=(low+hi) / 2;

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