编程访问:排序数组，算法证明

Question

下面是一个编程面试问题:给定3个排序数组。查找(x，y，z)，(其中x来自第1数组，y来自第2数组，z来自第3数组)，使得Max(x，y，z) - Min(x，y，z)最小。下面讨论这个问题：http://www.careercup.com/question?id=14805690

职业杯页面中讨论的一个可能的解决方案是：“接受三个指针。每个指针指向列表的第一个元素。然后找到它们的min。计算最大(Xyx)-Min(Xyz)。如果结果小于现在，请更改结果。增加包含它们最小值的数组的指针。”

我的问题是，我们如何证明这个算法的正确性？如果没有，我们能给出算法失败的情况吗？如果是这样的话，什么是正确的算法来解决这个问题的证明。

Answer 1

该算法具有循环不变，其中我们知道max(x, y, z) - min(x, y, z)的最小值，对于x、y或z的所有可能值都小于当前值。

从x开始，y和z是最小的，所以在开始时不变量是真的。最后，x、y和z是最大的可能，因此它们涵盖了所有可能的值，我们有了答案。

给定x、y、z的一些值，如果我们知道较小值的max(x, y, z) - min(x, y, z)的最优值，那么任何较好的值都需要增加x、y或z。

如果我们不增加它们的最小值，那么x、y或z的每一个较大的值都只能增加max(x, y, z) - min(x, y, z)的值，因为最大值只能增加，而最小值将保持不变。因此，最小值会增加到最小值，这个值可能会比我们拥有的值更好，这个值保持了循环不变。