GESP 5级客观题｜二分查找与二分答案｜课后作业

考试频率：高频。本卷共 6 题。

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

int binarySearch(int arr[], int left, int right, int target)
{
    while (left <= right)
    {
        ________________________________ // 在此处填入代码
            if (arr[mid] == target) return mid;
        else if (arr[mid] < target)
            left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

{{ select(1) }}

• int mid = left + (right - left) / 2;
• int mid = left;
• int mid = (left + right) / 2;
• int mid = right;

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

   {{ select(2) }}

• 对
• 错

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

int binary_search_last_occurrence(const vector<int>& lst, int target) {
    if (lst.empty()) return -1;
    int low = 0, high = lst.size() - 1;
    while (low < high) {
        int mid = (low + high + 1) / 2;
        if (lst[mid] <= target) {
            low = mid;
        } else {
            high = mid - 1;
        }
    }
    if (lst[low] == target)
        return low;
    else
        return -1;
}

{{ select(3) }}

• 当 lst 中存在重复的 target 时，该函数总能返回最后一个 target 的位置，即便 lst 全由相同元素组成
• 当 target 小于 lst 中所有元素时，该函数会返回 0
• 循环条件改为 while (low <= high) 程序执行效果相同，且能提高准确性
• 将代码中 (low + high + 1) / 2 修改为 (low + high) / 2 效果相同

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

   {{ select(4) }}

• "阶段1"的目标是寻找正整数 $n$ 可能的正完全平方根
• "阶段2"的目标是如果正整数 $n$ 没有正完全平方根，则在可能产生完全平方根附近寻找带小数点的平方根
• 代码 check_int = (long long)(result + 0.5) 是检查因浮点误差是否为正完全平方根
• 阶段2的二分法中 high_d - low_d >= epsilon 不能用于浮点数比较，会进入死循环

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

   {{ select(5) }}

• 对
• 错

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

int binarySearch(const std::vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;
    int times = 0;
    while (left <= right) {
        times ++;
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            cout << times << endl;
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    cout << times << endl;
    return -1;
}

{{ select(6) }}

• 2
• 5
• 3
• 4