Как я могу доказать правильность следующего алгоритма?

Question

Рассмотрим следующий алгоритм min, который принимает списки x,y в качестве параметров и возвращает z-й наименьший элемент в объединении x и y. Предварительные условия: X и Y - отсортированные списки целых в порядке возрастания, и они не пересекаются.

Обратите внимание, что это псевдокод, поэтому индексирование начинается с 1, а не с 0.

Min(x,y,z):
    if z = 1:
        return(min(x[1]; y[1]))
    if z = 2:
        if x[1] < y[1]:
            return(min(x[2],y[1]))
        else:
            return(min(x[1], y[2]))

q = Ceiling(z/2) //round up z/2

if x[q] < y[z-q + 1]:
    return(Min(x[q:z], y[1:(z - q + 1)], (z-q +1)))
else:
    return(Min(x[1:q], B[(z -q + 1):z], q))

Я могу доказать, что он заканчивается, потому что z продолжает уменьшаться на 2 и в конечном итоге достигнет одного из базовых случаев, но я не могу доказать частичную корректность.

Answer 1

Ваш код неверен.

Рассмотрим следующий вход:

x = [0,1]
y = [2]
z = 3

Вы тогда получаете q = 2 и в if пункт, который следует, доступ y[z-q+1]т.е. y[2], Это нарушение границ массива.