首页 › 题库 › GESP编程能力等级认证 › 5.1 二分查找

GESP-C++五级 题库

共 14 道题 · 按题型筛选,点「查看答案」核对解析
章节 5.1 二分查找 清除
1 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 5.1 二分查找

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

// 判断:在不超过 K 次切割内,是否能让每段长度 <= x 
bool check(int L, int K, int x) { 
    int cuts = (L - 1) / x; 
    return cuts <= K; 
} 
// 二分查找最小可行的 x 
int binary_cut(int L, int K) { 
    int l = 1, r = L; 
    while (l < r) { 
        int mid = l + (r - l) / 2; 
        ________________________________ // 在此处填入代码 
    } 
    return l; 
} 
int main() { 
    int L = 10; // 木头长度 
    int K = 2; // 最多切 K 刀 
    cout << binary_cut(L, K) << endl; 
    return 0; 
}
A
if (check(L, K, mid)) 
    r = mid; 
else 
    l = mid + 1;
B
if (check(L, K, mid)) 
    r = mid+1; 
else 
    l = mid + 1;
C
if (check(L, K, mid)) 
    r = mid + 1; 
else 
    l = mid - 1;
D
if (check(L, K, mid)) 
    r = mid + 1; 
else 
    l = mid;
答案与解析
正确答案:A
确定最小的正整数 x,使得将长度为 L 的木头切分为 K 段后,每段长度不超过 x。使用二分法在合理范围内查找 x,每次取中点 mid 作为候选值,通过 check 函数判断在最多 K 次切割下是否能保证所有段长度 ≤ mid。若判断成立,则说明 mid 可行,搜索更小的值;否则搜索更大的值。更新边界时需保持搜索区间的有效性,确保最终收敛到最小可行解。
题目详情
2 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 5.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;
}
A
int mid = left + (right - left) / 2;
B
int mid = left;
C
int mid = (left + right) / 2;
D
int mid = right;
答案与解析
正确答案:A

计算 mid 需要满足:

正确性:必须保证 mid 是当前区间的中间位置。

安全性:避免整数溢出(当 left 和 right 很大时,left + right 可能溢出)。

选项A:int mid = left + (right - left) / 2,数学等价于选项C,但是通过 right - left 避免直接计算 left + right,防止溢出。

题目详情
3 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 5.1 二分查找

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

int binary_search(vector<int>& nums, int target) {
	int left = 0;
	int right = nums.size() - 1;
	
	while (left <= right) {
		int mid = left + (right - left) / 2;
		
		if (nums[mid] == target) {
			return mid;
		}
		else if (nums[mid] < target) {
			left = mid + 1;
		}
		else {
			right = mid - 1;
		}
	}
	
	return -1; // 如果找不到目标元素,返回-1
}


A
1
B
2
C
3
D
4
答案与解析
正确答案:C

模拟即可,

第一次:mid=5,nums[5]=17,此时小于要查找的31,所以left=6。

第二次:mid=8,nums[8]=52,此时大于要查找的31,所以right=7。

第三次:mid=6,nums[6]=31,找到要查找的值,结束。

题目详情
4 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 5.1 二分查找

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

int binary_search(vector<int>& nums, int target) {
	int left = 0;
	int right = nums.size() - 1;
	while (left <= right) {
		int mid = (left + right) / 2;
		if (nums[mid] == target) {
			return mid;
		} else if (nums[mid] < target) {
			left = mid + 1;
		} else {
			right = mid - 1;
		}
	}
	return -1; // 如果找不到目标元素,返回-1
}
A
52, 61, 81, 90
B
52, 79, 90, 81
C
39, 79, 90, 81
D
39, 79, 90
答案与解析
正确答案:C

第一次迭代:

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

题目详情
5 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 5.1 二分查找

给定序列: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;
}
A
2
B
5
C
3
D
4
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
6 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 5.1 二分查找

下面C++代码用于有序 list 的二分查找,有关说法错误的是(   )。

A

代码采用二分法实现有序 list 的查找

B

代码采用分治算法实现有序 list 的查找

C

代码采用递归方式实现有序 list 的查找

D

代码采用动态规划算法实现有序 list 的查找

答案与解析
正确答案:D
这道题暂未补解析。
题目详情
7 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 5.1 二分查找

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

A
对
B
错
答案与解析
正确答案:对
二分查找的前提是数据有序,因其每次比较后可排除一半元素,依赖序列的单调性实现对数时间定位。若数据无序,无法直接应用二分查找。排序操作的时间复杂度通常为O(n log n),而单次线性查找的时间复杂度为O(n)。在仅需查找一次的情况下,执行排序的成本高于直接遍历。因此,为单次查找引入排序会改变整体操作的时间开销结构。是否执行排序取决于原始数据状态与后续操作需求,但排序本身不是二分查找的必要前置步骤,而是条件满足手段。
题目详情
8 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 5.1 二分查找

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

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
9 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 5.1 二分查找

查字典这个小学生必备技能,可以把字典视为一个已排序的数组。

假设小杨要查找一个音首字母为 g 的单词,他首先翻到字典约一半的页数,发现该页的首字母是 m ,由于字母表中 g 位于 m 之前,所以排除字典后半部分,查找范围缩小到前半部分;不断重复上述步骤,直至找到首字母为 g 的页码。

这种查字典的一系列操作可看作二分查找。( )

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
10 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 5.1 二分查找

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

A
对
B
错
答案与解析
正确答案:错

二分查找(Binary Search)是一种高效的查找算法,其前提条件:输入数组 必须是有序的。

题目详情
11 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 5.1 二分查找

二分查找仅适用于数组而不适合链表,因为二分查找需要跳跃式访问元素,链表中执行跳跃式访问的效率低。

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
12 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 5.1 二分查找

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

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
13 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 5.1 二分查找

二分查找要求被搜索的序列是有序的,否则无法保证正确性。

A
对
B
错
答案与解析
正确答案:对

二分查找的前提条件是,序列有序。

题目详情
14 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 5.1 二分查找

二分查找要求被搜索的序列是有序的,否则无法保证正确性。(   )

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情