Stop learning useless algorithms, go and solve some problems, learn how to use binary search.
并不是对这两个算法的详细介绍 只是随便记点相关的东西
STL 自带的二分查找
lower_bound 返回首个不小于指定值的元素
upper_bound 返回首个大于指定值的元素
两者都要求元素按升序排列
除了数组，也可以对内部元素有序的 STL 容器使用
但不要像我一样试图在 priority_queue 之类的东西上跑二分（
我们知道三分法可以找凸（凹）函数的最值
然后两个凸函数取 min 还是凸函数（凹函数则取 max ）
其实是数学性质 按单调区间分类讨论即可证明
做题时可能会遇到吧
另外两个凸函数相加并不一定是凸函数
CSP-S 2021 T1 就是个典型反例（虽然数据过水导致三分法可以 95pts
三分法对求值的利用效率并不高
可以采用黄金分割对其进行优化
比如下面这个区间，设其长度 \(R-L=1\)
如果查找范围缩小至 \([Lmid,R]\) ，我们希望 \(Rmid\) 恰好成为新的 \(Lmid\) ，这样就可以减少一次求值
显然可以列出方程： \(\dfrac k{1-k}=\dfrac{1-2k}k\)
解得 \(k_1=\dfrac{3-\sqrt5}2,k_2=\dfrac{3+\sqrt5}2\) （舍去 \(k_2\) ）
所以令 \(Lmid=\dfrac{3-\sqrt5}2,Rmid=\dfrac{\sqrt5-1}2\) 即可，也就是取当前区间的两个黄金分割点
一些卡步数的交互题可能会用这个技巧
或许也能用来卡常（没写过 不知道是否有效果）