笔试模拟:完善程序

10 分钟

完善程序题的正确顺序是:先认出"这是什么算法",再逐个空去推。认出算法后,每个空的作用就有了上下文——空通常出现在循环边界、状态更新语句、返回值这三处。看变量名(lrmid 基本就是二分)和整体结构来定位。

下面这段一眼是二分查找,空位也就顺理成章:

int find(int a[], int n, int x) {
    int l = 0, r = n - 1;
    while (l <= r) {
        int mid = (l + r) / 2;     // 空1:取中点
        if (a[mid] == x) return mid;
        if (a[mid] < x) l = mid + 1; // 空2:目标在右半段
        else r = mid - 1;
    }
    return -1;
}

最关键的坑:l = mid + 1 / r = mid - 1 必须和 while (l <= r) 这套闭区间写法配套,任何一处不一致都会导致死循环或漏掉答案。填完千万别直接交,拿一组小数据(比如找存在的、找不存在的各一个)手动代进去验算一遍。

小纸条

填完用小数据验算一遍。

登录 后可看答案

笔试模拟:完善程序 · 考级冲刺 · op599 课程