CSP-J 卷

设有 $100$ 个已排好序的数据元素，采用折半查找时，最大比较次数为（ ）。

在二分查找算法中，如果有序列表中有 N 个元素，其时间复杂度是（ ）。

若用二分法在 $[1, 100]$ 内猜数，最多需要猜（ ）次。

二分查找适用于对无序数组和有序数组的查找。

查字典这个小学生必备技能，可以把字典视为一个已排序的数组。假设小杨要查找一个音首字母为 g 的单词，他首先翻到字典约一半的页数，发现该页的首字母是 m ，由于字母表中 g 位于 m 之前，所以排除字典后半部分，查找范围缩小到前半部分；不断重复上述步骤，直至找到首字母为 g 的页码。这种查字典的一系列操作可看作二分查找。

在 C++ 中，可以使用二分法查找链表中的元素。

下面 C++ 代码用于有序 list 的二分查找，有关说法错误的是（ ）。

01int _binarySearch(vector<int>lst, int Low, int High, int Target)
02{
03    if (Low > High)
04        return -1;
05    int Mid = (Low + High) / 2;
06    if (Target == lst[Mid])
07        return Mid;
08    else if (Target < lst[Mid])
09        return _binarySearch(lst, Low, Mid - 1, Target);
10    else
11        return _binarySearch(lst, Mid + 1, High, Target);
12}
13int bSearch(vector<int>lst, int Val)
14{
15    return _binarySearch(lst, 0, lst.size(), Val);
16}

小杨在生日聚会时拿一块 H*W 的巧克力招待来的 K 个小朋友，保证每位小朋友至少能获得一块相同大小的巧克力。那么小杨想分出来最大边长的巧克力可以使用二分法。

给定序列：$1, 3, 6, 9, 17, 31, 39, 52, 61, 79, 81, 90, 96$。使用以下代码进行二分查找查找元素 82 时，需要循环多少次，即最后输出的 times 值为（ ）。

01int binarySearch(const std::vector<int>& arr, int target) {
02    int left = 0;
03    int right = arr.size() - 1;
04    int times = 0;
05    while (left <= right) {
06        times ++;
07        int mid = left + (right - left) / 2;
08        if (arr[mid] == target) {
09            cout << times << endl;
10            return mid;
11        } else if (arr[mid] < target) {
12            left = mid + 1;
13        } else {
14            right = mid - 1;
15        }
16    }
17    cout << times << endl;
18    return -1;
19}

根据下述二分查找法，在排好序的数组 $1, 3, 6, 9, 17, 31, 39, 52, 61, 79, 81, 90, 96$ 中查找数值 $82$，和 $82$ 比较的数组元素分别是（ ）。

01int binary_search(vector<int>& nums, int target) {
02    int left = 0;
03    int right = nums.size() - 1;
04    while (left <= right) {
05        int mid = (left + right) / 2;
06        if (nums[mid] == target) {
07            return mid;
08        } else if (nums[mid] < target) {
09            left = mid + 1;
10        } else {
11            right = mid - 1;
12        }
13    }
14    return -1; // 如果找不到目标元素，返回-1
15}

根据下述二分查找法，在排好序的数组 $1, 3, 6, 9, 17, 31, 39, 52, 61, 79$ 中查找数值 $31$，循环 while (left <= right) 执行的次数为（ ）。

01int binary_search(vector<int>& nums, int target) {
02    int left = 0;
03    int right = nums.size() - 1;
04
05    while (left <= right) {
06        int mid = left + (right - left) / 2;
07
08        if (nums[mid] == target) {
09            return mid;
10        }
11        else if (nums[mid] < target) {
12            left = mid + 1;
13        }
14        else {
15            right = mid - 1;
16        }
17    }
18    return -1; // 如果找不到目标元素，返回-1
19}

给定一个长度为 $n$ 的有序数组 nums，其中所有元素都是唯一的。下面的函数返回数组中元素 target 的索引。关于上述函数，描述不正确的是（ ）。

01int binarySearch(vector<int> &nums, int target, int left, int right) {
02    if (left > right) {
03        return -1;
04    }
05
06    int middle = left + ((right - left) / 2);
07    if (nums[middle] == target) {
08        return middle;
09    }
10    else if (nums[middle] < target) {
11        return binarySearch(nums, target, middle + 1, right);
12    }
13    else
14        return binarySearch(nums, target, left, middle - 1);
15}
16
17int Find(vector<int> &nums, int target) {
18    int n = nums.size();
19    return binarySearch(nums, target, 0, n - 1);
20}

给定一个长度为 $n$ 的有序数组 nums，其中可能包含重复元素。下面的函数返回数组中某个元素 target 的左边界，若数组中不包含该元素，则返回 $-1$。例如在数组 nums = [5,7,7,8,8,10] 中查找 target=8，函数返回 $8$ 在数组中的左边界的索引为 $3$。则横线上应填写的代码为（ ）。

01int getLeftBoundary(vector<int>& nums, int target) {
02    int left = 0;
03    int right = nums.size() - 1;
04
05    while (left < right) {
06        int middle = left + ((right - left) / 2);
07        if (target <= nums[middle])
08            ____________   // 在此处填入代码
09        else
10            left = middle+1;
11    }
12
13    return nums[left]==target?left:-1;
14}

对有序数组 {5,13,19,21,37,56,64,75,88,92,100} 进行二分查找，成功查找元素 $19$ 的比较次数是 $2$。

下面代码实现了二分查找算法，在数组 arr 找到目标元素 target 的位置，则横线上能填写的最佳代码是（ ）。

01int binarySearch(int arr[], int left, int right, int target) {
02    while (left <= right) {
03        ____________      // 在此处填入代码
04        if (arr[mid] == target)
05            return mid;
06        else if (arr[mid] < target)
07            left = mid + 1;
08        else
09            right = mid - 1;
10    }
11    return -1;
12}

二分查找依赖数据的有序性，通过循环逐步缩减一半搜索区间来进行查找，且仅适用于数组或基于数组实现的数据结构。

下面代码尝试在有序数组中查找第一个大于等于 $x$ 的元素位置。如果没有大于等于 $x$ 的元素，返回 arr.size()。以下说法正确的是（ ）。

01int lower_bound(vector<int>& arr, int x) {
02    int l = 0, r = arr.size();
03    while(l < r) {
04        int mid = l + (r - l) / 2;
05        if(arr[mid] >= x) r = mid;
06        else l = mid + 1;
07    }
08    return l;
09}

小杨要把一根长度为 $L$ 的木头切成 $K$ 段，使得每段长度小于等于 $x$。已知每切一刀只能把一段木头分成两段，他用二分法找到满足条件的最小 $x$（$x$ 为正整数），则横线处应填写（ ）。

01// 判断：在不超过 K 次切割内，是否能让每段长度 <= x
02bool check(int L, int K, int x) {
03    int cuts = (L - 1) / x;
04    return cuts <= K;
05}
06
07// 二分查找最小可行的 x
08int binary_cut(int L, int K) {
09    int l = 1, r = L;
10    while (l < r) {
11        int mid = l + (r - l) / 2;
12        ____________      // 在此处填入代码
13    }
14    return l;
15}
16
17int main() {
18    int L = 10;   // 木头长度
19    int K = 2;    // 最多切 K 刀
20
21    cout << binary_cut(L, K) << endl;
22    return 0;
23}

二分查找仅适用于有序数据。若输入数据无序，当仅进行一次查找时，为了使用二分而排序通常不划算。

在升序数组中查找第一个大于等于 x 的位置，下面循环中横线应填（ ）。

01int lowerBound(const vector<int>& a, int x){
02    int l=0, r=a.size();
03    while(l<r){
04        int mid = l + (r - l)/2;
05        if(a[mid] >= x)  ____________;
06        else l = mid + 1;
07    }
08    return l;
09}

若数组 a 已按升序排列，则下面代码可以正确实现"在 a 中查找第一个大于等于 x 的元素的位置"。

01int lowerBound(vector<int>& a, int x){
02    int l=0, r=a.size();
03    while(l < r) {
04        int mid = (l + r) / 2;
05        if( a[mid] >= x) r = mid;
06        else l = mid + 1;
07    }
08    return l;
09}

在一个有序数组中查找第一个大于或等于 x 的元素位置，横线处应填写（ ）。

01int lowerBound(vector<int>& a, int x) {
02    int l = 0, r = a.size();
03    while (l < r) {
04        int mid = l + (r - l) / 2;
05        if (a[mid] >= x) ________________; // 在此处填入代码
06        else l = mid + 1;
07    }
08    return l;
09}

二分查找不仅可以应用于有序数组，也可以在不增加时间复杂度的情况下应用于有序的单链表，因为链表也支持 $O(1)$ 时间内的随机访问。

下面的 C++ 代码用于在升序数组 lst 中查找目标值 target 最后一次出现的位置。相关说法，正确的是（ ）。

01int binary_search_last_occurrence(const vector<int>& lst, int target) {
02    if (lst.empty()) return -1;
03
04    int low = 0, high = lst.size() - 1;
05
06    while (low < high) {
07        int mid = (low + high + 1) / 2;
08        if (lst[mid] <= target) {
09            low = mid;
10        } else {
11            high = mid - 1;
12        }
13    }
14
15    if (lst[low] == target)
16        return low;
17    else
18        return -1;
19}

有关下面 C++ 代码的说法，错误的是（ ）。

01double sqrt_binary(long long n, double epsilon = 1e-10) {
02    if (n < 0) {
03        throw invalid_argument("输入必须为非负整数");
04    }
05
06    if (n == 0 || n == 1) return n;
07
08    // 阶段 1
09    long long low = 1, high = n;
10    long long k = 0;
11
12    while (low <= high) {
13        long long mid = (low + high) / 2;
14        long long mid_sq = mid * mid;
15
16        if (mid_sq == n) {
17            return mid;
18        } else if (mid_sq < n) {
19            k = mid;
20            low = mid + 1;
21        } else {
22            high = mid - 1;
23        }
24    }
25
26    long long next_k = k + 1;
27    if (next_k * next_k == n) {
28        return next_k;
29    }
30
31    // 阶段 2
32    double low_d = (double)k;
33    double high_d = (double)(k + 1);
34    double mid;
35
36    while (high_d - low_d >= epsilon) {
37        mid = (low_d + high_d) / 2;
38        double mid_sq = mid * mid;
39
40        if (mid_sq < n) {
41            low_d = mid;
42        } else {
43            high_d = mid;
44        }
45    }
46
47    double result = (low_d + high_d) / 2;
48    long long check_int = (long long)(result + 0.5);
49    if (check_int * check_int == n) {
50        return check_int;
51    }
52
53    return result;
54}

给定一个 $n \times n$ 的矩阵 matrix，矩阵的每一行和每一列都按升序排列。函数 countLE 返回矩阵中第 $k$ 小的元素，则两处横线上应分别填写（ ）。

01// 统计矩阵中 <= x 的元素个数：从左下角开始
02int countLE(const vector<vector<int>>& matrix, int x) {
03    int n = (int)matrix.size();
04    int i = n - 1, j = 0, cnt = 0;
05    while (i >= 0 && j < n) {
06        if (matrix[i][j] <= x) {
07            cnt += i + 1;
08            ++j;
09        }
10        else {
11            --i;
12        }
13    }
14    return cnt;
15}
16
17int kthSmallest(vector<vector<int>>& matrix, int k) {
18    int n = (int)matrix.size();
19    int lo = matrix[0][0];
20    int hi = matrix[n - 1][n - 1];
21    while (lo < hi) {
22        int mid = lo + (hi - lo) / 2;
23        if (countLE(matrix, mid) >= k) {
24            ____________        // 在此处填入代码
25        } else {
26            ____________        // 在此处填入代码
27        }
28    }
29    return lo;
30}

在二叉排序树（Binary Search Tree，BST）中查找元素 $50$，从根节点开始：若根值为 $60$，则下一步应去搜索：

下面 search 函数的平均时间复杂度为（ ）。

01int search(int n, int * p, int target) {
02    int low = 0, high = n;
03    while (low < high) {
04        int middle = (low + high) / 2;
05        if (target == p[middle]) {
06            return middle;
07        } else if (target > p[middle]) {
08            low = middle + 1;
09        } else {
10            high = middle;
11        }
12    }
13    return -1;
14}

下面程序的运行结果为（ ）。

01++
02#include <iostream>
03
04int query(int n, int *a, int x) {
05    int l = 0, r = n;
06    while (l < r) {
07        int mid = l + (r - l) / 2;
08        if (a[mid] >= x) r = mid;
09        else l = mid + 1;
10    }
11
12    if (l == n) return -1;
13    return l;
14}
15
16int main() {
17    int n = 10;
18    int x = 3;
19    int num[] = {1, 2, 2, 3, 3, 4, 5, 5, 6, 7};
20    
21    std::cout << query(n, num, x) << "\n";
22    return 0;
23}

在升序数组中用二分查找第一个大于等于 $x$ 的位置。若当前中点 $mid$ 满足 $a[mid] < x$，下一步应（ ）。

给定 double 类型的变量 $x$，且其值⼤于等于 ，我们可以通过⼆分法求出的 $\sqrt{x}$ 近似值

若能写出判定函数 check(x)，表示“答案为 $x$ 时是否可行”，即使 check(x) 不满足单调性，也一定可以使用二分答案求最优解。