algs4-1.4.10: 自测Case不全, 导致我没有给出正确答案

1.4.10修改二分查找算法，使之总是返回和被查找的键匹配的索引最小元素(且仍然能够保证对数级别的运行时间)。

设计用例, 确认初始版本的问题

初始版本如下:

public static int rankBase(int key, int[] a) {
    return rankBase(key, a, 0, a.length - 1);
}

public static int rankBase(int key, int[] a, int lo, int hi) {
    // 如果 key 存在于 a[] 中, 它的索引不会小于lo且不会大于hi
    if (lo > hi)
        return -1;
    int mid = lo + (hi - lo) / 2;

    if (key < a[mid]) {
        return rank(key, a, lo, mid - 1);
    } else if (key > a[mid]) {
        return rank(key, a, mid + 1, hi);
    } else {
        return mid;
    }
}

我为它设计了一个简单的测试用例, 确认问题, 确实存在:

int[] a = { 2, 2 };
int[] b = { 2, 2, 2 };
int[] c = { 2, 2, 2, 2 };

// sort the array
Arrays.sort(a);
Arrays.sort(b);
Arrays.sort(c);

int key = 2;
/**
 * 修改前, 输出:
 * [2, 2] rank = 0
 * [2, 2, 2] rank = 1
 * [2, 2, 2, 2] rank = 1
 */
StdOut.println("原始版本:");
StdOut.println(Arrays.toString(a) + "\t\trank = " + rankBase(key, a));
StdOut.println(Arrays.toString(b) + "\trank = " + rankBase(key, b));
StdOut.println(Arrays.toString(c) + "\trank = " + rankBase(key, c));
StdOut.println(Arrays.toString(d) + "\trank = " + rankBase(key, d));

基于测试用例, 完善代码.

我初始优化后的代码如下:

public static int rank(int key, int[] a) {
    return rank(key, a, 0, a.length - 1);
}

public static int rank(int key, int[] a, int lo, int hi) {
    // 如果 key 存在于 a[] 中, 它的索引不会小于lo且不会大于hi
    if (lo > hi)
        return -1;
    int mid = lo + (hi - lo) / 2;

    if (mid - 1 >= 0 && key == a[mid - 1]) {
        return mid - 1;
    }

    if (key < a[mid]) {
        return rank(key, a, lo, mid - 1);
    }

    if (key > a[mid]) {
        return rank(key, a, mid + 1, hi);
    }

    return mid;
}

修改后, 既有测试用例, 是跑通了:

/* 
* (我的答案)修改后, 输出(我的初版答案不对.):
* [2, 2] rank = 0
* [2, 2, 2] rank = 0
* [2, 2, 2, 2] rank = 0
*/
StdOut.println("我自己的改进版本:");
StdOut.println(Arrays.toString(a) + "\t\trank = " + rank(key, a));
StdOut.println(Arrays.toString(b) + "\trank = " + rank(key, b));
StdOut.println(Arrays.toString(c) + "\trank = " + rank(key, c));

GPT4 指出了我的错误: 找到的不一定是最左侧的索引.

GPT4给出的进一步完善的版本:

public static int gptRank(int key, int[] a) {
    return gptRank(key, a, 0, a.length - 1);
}

public static int gptRank(int key, int[] a, int lo, int hi) {
    // 如果 key 不存在于 a[] 中, 它的索引不会小于lo且不会大于hi
    if (lo > hi)
        return -1;
    int mid = lo + (hi - lo) / 2;

    if (key < a[mid]) {
        return rank(key, a, lo, mid - 1);
    } else if (key > a[mid]) {
        return rank(key, a, mid + 1, hi);
    } else if (mid - 1 >= 0 && a[mid - 1] == key) {
        return rank(key, a, lo, mid - 1); // 若找到匹配的元素, 继续在左区间查找，直至找不到为止
    } else {
        return mid;
    }
}

为了快速修改 ChatGPT4 的答案, 我适当完善了下测试Case:

public static void main(String[] args) {
    int[] a = { 2, 2 };
    int[] b = { 2, 2, 2 };
    int[] c = { 2, 2, 2, 2 };

    // 初始设计我的改进版本时, 没有d的值.
    int[] d = { 2, 2, 2, 2, 2 };

    // sort the array
    Arrays.sort(a);
    Arrays.sort(b);
    Arrays.sort(c);
    Arrays.sort(d);

    int key = 2;
    /**
     * 修改前, 输出:
     * [2, 2] rank = 0
     * [2, 2, 2] rank = 1
     * [2, 2, 2, 2] rank = 1
     * 
     * --------
     * 
     * (我的答案)修改后, 输出(我的初版答案不对.):
     * [2, 2] rank = 0
     * [2, 2, 2] rank = 0
     * [2, 2, 2, 2] rank = 0
     * [2, 2, 2, 2, 2] rank = 1
     */
    StdOut.println("原始版本:");
    StdOut.println(Arrays.toString(a) + "\t\trank = " + rankBase(key, a));
    StdOut.println(Arrays.toString(b) + "\trank = " + rankBase(key, b));
    StdOut.println(Arrays.toString(c) + "\trank = " + rankBase(key, c));
    StdOut.println(Arrays.toString(d) + "\trank = " + rankBase(key, d));

    StdOut.println("我自己的改进版本:");
    StdOut.println(Arrays.toString(a) + "\t\trank = " + rank(key, a));
    StdOut.println(Arrays.toString(b) + "\trank = " + rank(key, b));
    StdOut.println(Arrays.toString(c) + "\trank = " + rank(key, c));
    StdOut.println(Arrays.toString(d) + "\trank = " + rank(key, d));

    /*
     * GPT4 的输出
     * [2, 2] rank = 0
     * [2, 2, 2] rank = 0
     * [2, 2, 2, 2] rank = 0
     * [2, 2, 2, 2, 2] rank = 0
     */
    StdOut.println("GPT4的进一步改进版本:");
    StdOut.println(Arrays.toString(a) + "\t\trank = " + gptRank(key, a));
    StdOut.println(Arrays.toString(b) + "\trank = " + gptRank(key, b));
    StdOut.println(Arrays.toString(c) + "\trank = " + gptRank(key, c));
    StdOut.println(Arrays.toString(d) + "\trank = " + gptRank(key, d));
}

显而易见, ChatGPT4 确实是正确的. 我初始给出的测试Case, 自以为相对完备, 但是其实都属于只需要”二分”一次的特殊Case.

小感: 把 AI 当辅助工具. 它不需要完美,不需要全知全能. 只要靠谱程度在一个可接受的范围内, 就可以试着使用.

问题本身, 后续在设计测试Case时, 要有更多的权衡.但是这次最让我惊讶的是: GPT4, 竟然能基于我的思路,继续往后分析. 说实话, 我有些困惑. 这和已经接触的机器学习的知识, 很不一样. 而且我相信, 很难做到. 我不太确定, GPT4 是训练方法, 还是输入数据发生了变化. 不太像是输入数据的变化引起的. 因为针对这个问题, GPT3 和 bard 的回答, 都是不正确的. 而 GPT3 和 bard 不太可能没机会获取比 GPT4 更多的高质量数据.

GPT4的训练方法和数据, 都是不公开的. 这就意味着, 我无法简单的复刻一些GPT4. 但是基于入门级的机器学习的知识, 我知道一个简单的事实: 模型的训练过程, 有一定的随机性; 但是训练生成的模型, 一旦在稳定性和质量上, 能相对满足自己的需要, 就是可以直接使用的. 这有点像, 我们可能不知道某款药物的生产过程, 但是如果药物本身已经确认会对某些病症起作用, 那我们就可以基于它来治疗.(当然, 药物的例子不太妥当, 药物的验证, 更严格.)

本来, 我是对 AI 非常不太看好的. 比如语音合成, 若干技术流派, 但是依然我能很明显地听出 “机器腔”; 再比如 “自动驾驶”, 特斯拉若干年的许诺之后, 依然无法实现 “完全的自动驾驶”.

但是现在, 我可能要适当调整以下自己的看法. AI 不必是全知全能, 无所不包的. 只要AI能解决某个自己需要解决的问题, 那它就是有价值的. 这就像: 制造一个会自动做各种美味的锅, 可能很难很难; 但是一个合适的锅, 确实是提高居家做饭的人的体验的.我们会因为锅不是自动做饭, 就不去尝试选购更合适的锅吗?

简言之: 把 AI 看作一个工具. 我们不需要强求一个 AI 全知全能, 无所不知; 我们只需要找到一个能在可控范围内, 替自己更好地做某事的 AI 工具即可.

当然, 我们首先要搞明白, 自己究竟要做的是什么. 比如我现在, 真正要做的是算法学习和思维训练. 显而易见, 我应该总是先尝试自己独立解题, 再和 AI 去交互, “对答案”.

无论如何, 真的不敢相信, GPT4, 竟然能在算法学习领域, 提供这么大的帮助. 更广阔地去想: GPT 或许能真正意义上解决 “教育资源” 的不公平性.或许未来不再是捐钱, 而是直接捐 GPT 额度, 捐数据中心, 捐显卡…哈哈哈哈

期待. 期待能把 GPT4 真正搞糊涂的算法问题!

补充: GPT3 GPT4 bard 的回复:

GPT4: 目前看, 回复质量最高, 最稳定. 能顺着既有思路进一步优化的方式, 真的很厉害. 我怀疑一部分算法老师,都未必能做到这种程度.

gpt4_resp

GPT3: GPT3的回复不稳定. 如果你只能用 GPT3, 建议同一个问题, 多问几次.问题本身, 我初始问时, gpt3是认为我的解法是正确的.

gpt3_resp

bard: 它的回复, 都不对.不建议用.偶尔参考下, 也要慎重.

bard_resp