#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
  • 以上四条规则与升序数组完全相反