Как определить инвариант l oop в моей реализации двоичного поиска?

Question

bool binsearch(int x) {
    int i = 0, j = N;
    while(i < j) {
        int m = (i+j)/2;
        if(arr[m] <= x) {
            if(arr[m] == x)
                return true;
            i = m+1;
        }
        else {
            j = m;
        }
    }
    return false;
}

Это моя реализация бинарного поиска, которая возвращает true, если x находится в arr [0: N-1], или возвращает false, если x отсутствует в arr [0: N-1]. И мне интересно, как я могу определить правильный инвариант l oop, чтобы доказать, что эта реализация верна. Как я могу решить эту проблему? Большое спасибо: D

Answer 1

Подумайте о переменных, содержащих состояние в вашем l oop. В вашем случае это переменные i и j. Вы начинаете с того, что все элементы x), и все элементы> j и больше, чем x. Это тот инвариант, который вы пытаетесь сохранить.