proof - 如何证明以下算法的正确性？

Question

考虑以下算法 min ，它将列表 x,y 作为参数并返回 x 和 y 联合中的第 z 个最小元素。前置条件：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 = 2and，在后面的if子句中，访问y[z-q+1]，即y[2]。这是一个数组边界违规。