Исключение индекса вне границ в бинарном поиске

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, потому что тогда оно не прекратится длябольшое число не в массиве.

Answer 2

Проблема заключается в условии, при котором вы продолжаете цикл.Попробуйте изменить это:

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

на это:

while (hi>=low) {

Если hi < low, вы не хотите продолжать цикл независимо от двух других условий (одно из которых всегда будетбыть правдой, я думаю, если hi < low).