笔试模拟:完善程序
约 10 分钟
完善程序题的正确顺序是:先认出"这是什么算法",再逐个空去推。认出算法后,每个空的作用就有了上下文——空通常出现在循环边界、状态更新语句、返回值这三处。看变量名(l、r、mid 基本就是二分)和整体结构来定位。
下面这段一眼是二分查找,空位也就顺理成章:
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) 这套闭区间写法配套,任何一处不一致都会导致死循环或漏掉答案。填完千万别直接交,拿一组小数据(比如找存在的、找不存在的各一个)手动代进去验算一遍。
小纸条
填完用小数据验算一遍。
登录 后可看答案