程序一：闭区间精确查找

阅读程序并完成第 1～5 题。

int find_pos(int a[], int n, int x) {
    int l = 0, r = n - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (a[mid] == x) return mid;
        if (a[mid] < x) l = mid + 1;
        else r = mid - 1;
    }
    return -1;
}
int a[6] = {1, 3, 3, 5, 8, 13};

第 1 题

调用 find_pos(a,6,3) 返回多少？

{{ input(1) }}

---

第 2 题

调用 find_pos(a,6,4) 返回多少？

{{ input(2) }}

---

第 3 题

调用 find_pos(a,6,13) 返回多少？

{{ input(3) }}

---

第 4 题

把 l = mid + 1 错改为 l = mid，最可能造成的问题是（ ）。

{{ select(4) }}

• 一定数组越界
• 某些输入下区间不再缩小，循环无法结束
• 只能找到偶数
• 复杂度变为 $O(1)$

---

第 5 题

该函数的时间复杂度是（ ）。

{{ select(5) }}

• $O(1)$
• $O(\log n)$
• $O(n)$
• $O(n^2)$

---

程序二：第一个大于等于 x 的位置

阅读程序并完成第 6～10 题。

int lower_pos(int a[], int n, int x) {
    int l = 0, r = n;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] < x) l = mid + 1;
        else r = mid;
    }
    return l;
}
int a[6] = {1, 3, 3, 3, 7, 9};

第 6 题

调用 lower_pos(a,6,3) 返回多少？

{{ input(6) }}

---

第 7 题

调用 lower_pos(a,6,4) 返回多少？

{{ input(7) }}

---

第 8 题

调用 lower_pos(a,6,10) 返回多少？

{{ input(8) }}

---

第 9 题

循环结束时，答案同时由哪两个变量表示？（填写 变量1==变量2）

{{ input(9) }}

---

第 10 题

程序判断 a[mid] < x 的根本目的是（ ）。

{{ select(10) }}

• 排除 mid 及其左侧不可能成为答案的位置
• 排除 mid 右侧
• 寻找最后一个等于 x 的位置
• 交换相邻元素

---

程序三：二分答案

阅读程序并完成第 11～12 题。

bool ok(int x) {
    return 1LL * x * x >= 30;
}
int l = 0, r = 10;
while (l < r) {
    int mid = l + (r - l) / 2;
    if (ok(mid)) r = mid;
    else l = mid + 1;
}
cout << l;

第 11 题

程序输出多少？

{{ input(11) }}

---

第 12 题

表达式中写 1LL * x * x 的主要原因是（ ）。

{{ select(12) }}

• 把结果转成小数
• 避免先按 int 乘法造成溢出
• 使二分次数翻倍
• 保证 x 为正数

---