GESP-C++五级 题库
小杨要把一根长度为 L 的木头切成 K 段,使得每段长度小于等于 x 。已知每切一刀只能把一段木头分成两段,他用二分法找到满足条件的最小 x ( x 为正整数),则横线处应填写( )。
下面代码实现了二分查找算法,在数组 arr 找到目标元素 target 的位置,则横线上能填写的最佳代码是?( )
计算 mid 需要满足:
正确性:必须保证 mid 是当前区间的中间位置。
安全性:避免整数溢出(当 left 和 right 很大时,left + right 可能溢出)。
选项A:int mid = left + (right - left) / 2,数学等价于选项C,但是通过 right - left 避免直接计算 left + right,防止溢出。
根据下述二分查找法,在排好序的数组 1,3,6,9,17,31,39,52,61,79 中查找数值 31 ,循环while (left <= right) 执行的次数为( )。
模拟即可,
第一次:mid=5,nums[5]=17,此时小于要查找的31,所以left=6。
第二次:mid=8,nums[8]=52,此时大于要查找的31,所以right=7。
第三次:mid=6,nums[6]=31,找到要查找的值,结束。
根据下述二分查找法,在排好序的数组 1,3,6,9,17,31,39,52,61,79,81,90,96 中查找数值82,和82比较的数组元素分别是( )。
第一次迭代:
left = 0, right = 12,数组范围是整个数组。
mid = (0 + 12) / 2 = 6,即中间元素是39。
nums[mid] = 39,小于目标值82,所以更新 left = mid + 1 = 7。
第二次迭代:
left = 7, right = 12,数组范围缩小到[52, 61, 79, 81, 90, 96]。
mid = (7 + 12) / 2 = 9,即中间元素是79。
nums[mid] = 79,小于目标值82,所以更新 left = mid + 1 = 10。
第三次迭代:
left = 10, right = 12,数组范围缩小到[81, 90, 96]。
mid = (10 + 12) / 2 = 11,即中间元素是90。
nums[mid] = 90,大于目标值82,所以更新 right = mid - 1 = 10。
第四次迭代:
left = 10, right = 10,即只剩下一个元素81。
mid = (10 + 10) / 2 = 10,即中间元素是81。
nums[mid] = 81,小于目标值82,所以更新 left = mid + 1 = 11。
根据上述分析,与目标值82进行比较的数组元素依次是:39, 79, 90, 81
给定序列:1,3,6,9,17,31,39,52,61,79,81,90,96。使用以下代码进行二分查找查找元素 82时,需要循环多少次,即最后输出的 times 值为( )。
下面C++代码用于有序 list 的二分查找,有关说法错误的是( )。

代码采用二分法实现有序 list 的查找
代码采用分治算法实现有序 list 的查找
代码采用递归方式实现有序 list 的查找
代码采用动态规划算法实现有序 list 的查找
二分查找仅适用于有序数据。若输入数据无序,当仅进行一次查找时,为了使用二分而排序通常不划算。
二分查找依赖数据的有序性,通过循环逐步缩减一半搜索区间来进行查找,且仅适用于数组或基于数组实现的数据结构。2025.9-5
查字典这个小学生必备技能,可以把字典视为一个已排序的数组。
假设小杨要查找一个音首字母为 g 的单词,他首先翻到字典约一半的页数,发现该页的首字母是 m ,由于字母表中 g 位于 m 之前,所以排除字典后半部分,查找范围缩小到前半部分;不断重复上述步骤,直至找到首字母为 g 的页码。
这种查字典的一系列操作可看作二分查找。( )
二分查找适用于对无序数组和有序数组的查找。( )
二分查找(Binary Search)是一种高效的查找算法,其前提条件:输入数组 必须是有序的。
对有序数组 {5,13,19,21,37,56,64,75,88,92,100} 进行二分查找,成功查找元素 19 的比较次数是2。