Бинарный поиск - зачем мне каждый раз вычитать 1 / добавить 1 при изменении интервала?

Question

Я пытался понять, как работает бинарный поиск в последнее время.

У меня есть этот пример.

int CautareBinara(int x)
{
    int Sol = -1, Left = 0, Right = N;
    while(Left <= Right)
    {
        int Mid = (Left+Right) / 2;
        if(V[Mid] == x)
        {
            Sol = Mid;
            break;
        }
        if(V[Mid] > x)
            Right = Mid - 1;
        if(V[Mid] < x)
            Left = Mid + 1;
    }
    return Sol;
}

Я понял, я действительно понял, как он работает, но там это одна вещь, которую мне не хватает.

Зачем мне нужно вычитать 1 / добавить 1 в выражениях

Right = Mid - 1;
Left = Mid + 1;

Разве это не будет работать только с Right = Mid и Left = Середина?

Кажется, я этого не понимаю.

Я думаю, что мы делаем это, потому что мы уже протестировали v [Mid], поэтому мы можем уменьшить интервал на 1 единицу. Это причина?

Спасибо.

Answer 1

Ответ заключается в том, что вы определили интервал как строго между, так что можете сделать + -1, потому что вы проверили среднюю точку, так что это больше не является возможным ответом.

Но другая половина состоит в том, что у вас есть , чтобы сделать это, потому что если вы этого не сделаете, вы можете получить Left+1=Right, Right = (Left+Right) / 2 и V[Mid] > x, и тогда вы не сможете добиться прогресса. Вы попадаете в одну и ту же ситуацию ... и бесконечное l oop.

Мораль такова. Есть много способов закодировать бинарный поиск. Но если вы даже немного ошиблись в индексах, есть множество способов получить бесконечное значение l oop.