算法导论二分查找算法
算法导论:二分查找算法。比较简单的算法,ACM QQ群里看到的,通俗易懂。二分查找算法简单定义:在一个单调有序的集合中查找元素,每次将集合分为左右两部分,判断解在哪个部分中并调整集合上下界,重复直到找到目标元素·时间复杂度:,优于直接顺序查找例如513192137566475808892L环4Mid+High+513192137566475808892MidHigh513192137566475808892Lo|王ighMid参考程序待查找的元素,:数组集合大小,数组单调递增集合下界集合上界将集合分割为两部分查找到符合元素在右边部分,调整集合下界在左边部分,调整集合上界查找连续函数的写法待査找的值;所要查找的函数,在这里单调递增。需保证査找的值在区间范围内“区间下界”,“区间上界”,常见拓展对于某些问题,如果答案具有特定的范围,并且验证答案是否成立的函数具有单调性则可以在范围内对答案进行二分验证,从而快速确定答案。例:题目大意:有个人分块披萨,每个人要求分得的面积一样,且披萨只能被切开而不能重新组合,求每个人能分到的最大面积分析:对于每个确定的,可以计算出最多能满足的人数。因此得到一个单调递减的函数关系,并且的范围也可以确定为核心代码由于精度差问题,考虑先将面积转化为整数来二分最后结果为
下载地址
用户评论