#cspjc6. 二分查找函数专项
二分查找函数专项
二分查找函数专项
1.升序数组下的二分查找
在升序数组 [1, 3, 5, 5, 5, 7, 9] 中查找 5 的范围。
int a[7] = {1, 3, 5, 5, 5, 7, 9};
int first = lower_bound(a, a+7, 5) - a; // 返回 2
int last = upper_bound(a, a+7, 5) - a - 1; // 返回 4
bool exist = binary_search(a, a+7, 5); // true
例:关于升序数组的二分函数,正确的有()?{{ multiselect(1) }}
lower_bound返回第一个 大于等于 目标值的位置upper_bound返回第一个 大于 目标值的位置binary_search返回bool,但不能获取位置;要获取位置需用lower_bound- 若目标值大于所有元素,
lower_bound返回end(即a+n),减去首地址得到n - 三个函数的头文件均为
<algorithm>,且要求序列必须有序(默认升序)
2.降序数组下的二分查找(必须传 greater<>()) 核心难点
数组已按降序排列 [9, 8, 6, 6, 6, 5],想找数字 6 的范围。
int a[6] = {9, 8, 6, 6, 6, 5};
// 降序数组必须传入 greater<int>() 作为第四个参数
int first = lower_bound(a, a+6, 6, greater<int>()) - a; // 返回 2(第一个6)
int last = upper_bound(a, a+6, 6, greater<int>()) - a - 1; // 返回 4(最后一个6)
bool exist = binary_search(a, a+6, 6, greater<int>()); // true
例:关于降序数组使用二分查找,以下说法正确的有( )?{{ multiselect(2) }}
- 对降序数组使用默认的
lower_bound(不传第四个参数)结果是未定义的,不能得到正确答案 - 使用
greater<int>()时,lower_bound查找的是第一个 不大于(即<=)目标值的位置 - 使用
greater<int>()时,upper_bound查找的是第一个 小于(即<)目标值的位置 - 对于降序数组,
binary_search也必须传入greater<int>(),否则查找结果错误 greater<int>()必须包含头文件<functional>,同时也要包含<algorithm>
3.lower_bound/ upper_bound 结合 greater 的边界陷阱
降序数组 [5, 4, 3, 2, 1],分别查找不存在的值和边界值。
int a[5] = {5, 4, 3, 2, 1};
int p1 = lower_bound(a, a+5, 0, greater<int>()) - a; // 目标比所有元素都小
int p2 = lower_bound(a, a+5, 6, greater<int>()) - a; // 目标比所有元素都大
例:关于降序二分查找的返回边界,以下说法正确的有( )?{{ multiselect(3) }}
- 当目标值比所有元素都小时(如
0),lower_bound返回end(即索引n) - 当目标值比所有元素都大时(如
6),lower_bound返回begin(即索引0) - 在降序数组中,
upper_bound若目标值比所有元素都大,返回begin - 在降序数组中,
upper_bound若目标值比所有元素都小,返回end - 以上四条规则与升序数组完全相反