• 分享
  • 【第一弹】想学四段的看过来之二分答案&&二分

  • @ 2024-8-28 10:45:22

前言: 该讨论会分为多个:第一弹,第二弹; 以下为四段的大概: 1.浮点二分&&二分答案&&二分
<----------中间加一个贪心
2.STLSTL
3.数据结构
4.广度优先搜索
5.深度优先搜索强化&&高阶
6.动态规划
7.栈强化&&单调栈
8.线性动规
9.动态规划之多重背包,完全背包,滚动数组
10.图论
11.最小生成树&&并查集
12.最短路之dijkstra,kruskal
13.五段过度


1.浮点二分&&二分答案&&二分

1.1

定义

二分查找 (英语:binary search),也称折半搜索 (英语:half-interval search)、对数搜索 (英语:logarithmic search),是用来在一个有序数组中查找某一元素的算法。

1.1.2

过程

以在一个升序数组中查找一个数为例。
它每次考察数组当前部分的中间元素,如果中间元素刚好是要找的,就结束搜索过程;如果中间元素小于所查找的值,那么左侧的只会更小,不会有所查找的元素,只需到右侧查找;如果中间元素大于所查找的值同理,只需到左侧查找。

1.1.3

性质

时间复杂度

二分查找的最优时间复杂度为 O(1)O(1)
二分查找的平均时间复杂度和最坏时间复杂度均为 O(logn)O(\log n)。因为在二分搜索过程中,算法每次都把查询的区间减半,所以对于一个长度为nn的数组,至多会进行O(logn)O(\log n)次查找。

空间复杂度

迭代版本的二分查找的空间复杂度为O(1)O(1)
递归(无尾调用消除)版本的二分查找的空间复杂度为 O(logn)O(\log n)

1.1.4

实现

int binary_search(int start, int end, int key) {
    int ret = -1;  // 未搜索到数据返回-1下标
    int mid;
    while (start <= end) {
        mid = start + ((end - start) >> 1);  // 直接平均可能会溢出,所以用这个算法
        if (arr[mid] < key)
          start = mid + 1;
        else if (arr[mid] > key)
          end = mid - 1;
        else {  // 最后检测相等是因为多数搜索情况不是大于就是小于
          ret = mid;
          break;
        }
    }
    return ret;  // 单一出口
}

对于nn是有符号数的情况,当你可以保证n0n\ge 0时,n>>1n>>1n/2n/2指令数更少。


1.2

1.2.1

最大值最小化

注意,这里的有序是广义的有序,如果一个数组中的左侧或者右侧都满足某一种条件,而另一侧都不满足这种条件,也可以看作是一种有序(如果把满足条件看做11,不满足看做00,至少对于这个条件的这一维度是有序的)。换言之,二分搜索法可以用来查找满足某种条件的最大(最小)的值。

要求满足某种条件的最大值的最小可能情况(最大值最小化),首先的想法是从小到大枚举这个作为答案的「最大值」,然后去判断是否合法。若答案单调,就可以使用二分搜索法来更快地找到答案。因此,要想使用二分搜索法来解这种「最大值最小化」的题目,需要满足以下三个条件:

答案在一个固定区间内; 可能查找一个符合条件的值不是很容易,但是要求能比较容易地判断某个值是否是符合条件的; 可行解对于区间满足一定的单调性。换言之,如果xx是符合条件的,那么有x+1x + 1或者x1x - 1也符合条件。(这样下来就满足了上面提到的单调性) 当然,最小值最大化是同理的。

1.2.2

STL中的二分查找

C++ 标准库中实现了查找首个不小于给定值的元素的函数 std::lower_bound 和查找首个大于给定值的元素的函数std::upper_bound,二者均定义于头文件 中。
二者均采用二分实现,所以调用前必须保证元素有序。

所以,如果是无序的,那就sort一下

1.2.3

bsearchbsearch

bsearch函数为CC标准库实现的二分查找,定义在 <stdlib.h><stdlib.h>中。在C++C++标准库里,该函数定义在 <cstdlib><cstdlib>中。qsortqsortbsearchbsearchCC语言中唯二的两个算法类函数。
bsearchbsearch函数相比qsortqsort(看看这)的四个参数,在最左边增加了参数「待查元素的地址」。之所以按照地址的形式传入,是为了方便直接套用与qsortqsort相同的比较函数,从而实现排序后的立即查找。因此这个参数不能直接传入具体值,而是要先将待查值用一个变量存储,再传入该变量地址。
于是bsearchbsearch函数总共有五个参数:待查元素的地址、数组名、元素个数、元素大小、比较规则。比较规则仍然通过指定比较函数实。
bsearchbsearch函数的返回值是查找到的元素的地址,该地址为 void 类型。

注意:bsearchbsearch与上文的lower_boundupper_bound有两点不同:

1.当符合条件的元素有重复多个的时候,会返回执行二分查找时第一个符合条件的元素,从而这个元素可能位于重复多个元素的中间部分。 当查找不到相应的元素时,会返回NULLNULL。 用lower_bound可以实现与bsearchbsearch完全相同的功能,所以可以使用bsearchbsearch通过的题目,直接改写成 lower_bound同样可以实现。但是鉴于上述不同之处的第二点,例如,在序列124561、2、4、5、6中查找33bsearchbsearch实现lower_bound的功能会变得困难。

2.利用bsearchbsearch实现lower_bound的功能比较困难,是否一定就不能实现?答案是否定的,存在比较trickytricky的技巧。借助编译器处理比较函数的特性:总是将第一个参数指向待查元素,将第二个参数指向待查数组中的元素,也可以用 bsearchbsearch实现lower_bound 和 upper_bound,如下文示例。只是,这要求待查数组必须是全局数组,从而可以直接传入首地址。

int A[100005];  // 示例全局数组

// 查找首个不小于待查元素的元素的地址
int lower(const void *p1, const void *p2) {
  int *a = (int *)p1;
  int *b = (int *)p2;
  if ((b == A || compare(a, b - 1) > 0) && compare(a, b) > 0)
    return 1;
  else if (b != A && compare(a, b - 1) <= 0)
    return -1;  // 用到地址的减法,因此必须指定元素类型
  else
    return 0;
}

// 查找首个大于待查元素的元素的地址
int upper(const void *p1, const void *p2) {
  int *a = (int *)p1;
  int *b = (int *)p2;
  if ((b == A || compare(a, b - 1) >= 0) && compare(a, b) >= 0)
    return 1;
  else if (b != A && compare(a, b - 1) < 0)
    return -1;  // 用到地址的减法,因此必须指定元素类型
  else
    return 0;
}

因为现在的OIOI选手很少写纯CC,并且此方法作用有限,所以不是重点。对于新手而言,建议老老实实地使用C++C++中的lower_bound和upper_bound函数。


1.3

二分答案

解题的时候往往会考虑枚举答案然后检验枚举的值是否正确。若满足单调性,则满足使用二分法的条件。把这里的枚举换成二分,就变成了「二分答案」。


这篇文章就目前更新到这,想看STLSTL的要等我的“肝”回来再说吧

2 条评论

  • 1