<small id='evny2a8DCd'></small> <noframes id='fLsKJpT'>

  • <tfoot id='rbXopFemdc'></tfoot>

      <legend id='9TMEAJ'><style id='wSLyfZi'><dir id='mXubzY'><q id='7TYP82sqIr'></q></dir></style></legend>
      <i id='gsMLG1w'><tr id='KRIr1uPMb'><dt id='D6jKQC4NI'><q id='gITyrLd'><span id='Cp0US6M8'><b id='vhgarFn1O'><form id='jI69bEqJap'><ins id='CnHAgFt'></ins><ul id='sLTVh'></ul><sub id='PCIDp6d'></sub></form><legend id='72auSWvZT'></legend><bdo id='CEYKx'><pre id='PiHyhA'><center id='D2oVr3Jfa'></center></pre></bdo></b><th id='vi5S'></th></span></q></dt></tr></i><div id='Bsnfz0Qv'><tfoot id='7naJUXjMS'></tfoot><dl id='XDVRIB'><fieldset id='NISb'></fieldset></dl></div>

          <bdo id='C4fFT'></bdo><ul id='YpLHG'></ul>

          1. <li id='P1IFY'></li>
            登陆

            章鱼彩票网-二分查找及其变体

            admin 2019-05-14 266人围观 ,发现0个评论

            二分查找是一个功率很高的算法。一个杰出完结的二分查找算法,其时刻复杂度可以到达 (logn)

            (log⁡n),而空间复杂度只要 O(1)

            O(1)。特别地,二分查找算法的描绘非常简练。作为程序员,总是喜爱 clean and powerful 的东西。因而,二分查找无疑对程序员有巨大的吸引力。

            依照 Knuth 的说法,「虽然第一个二分查找算法早在1946年就被宣布,但第一个没有bug的二分查找算法却是在12年后才被宣布出来」。

            此篇咱们评论二分查找算法的原理及其各种变体的完结。

            算法描绘

            二分查找是针对支撑随机拜访的有序数据集进行查找操作的算法。最基本的二分查找,查找的是等于方针元素的元素在数据会集的方位。它的描绘非常简略:

            • 减半取中,判别元素与方针元素的巨细联系
            • 小于——往前持续减半
            • 大于——往后持续减半
            • 等于——回来

            此处要注意二分查找的适用场景:

            • 依靠次序表结构
            • 数据自身有必要有序
            • 数据量相对比较元素的开支要足够大——否则遍历即可
            • 数据量相对内存空间不能太大——否则次序表装不下

            二分查找的完结

            仿制

            #include 
            #include
            template
            typename ValueT = typename std::iterator_traits::value_type,
            typename Compare = std::less>
            IterT bsearch(IterT first,
            IterT last,
            ValueT target,
            Compare comp = Compare()) {
            IterT result = last;
            while (std::distance(first, last) > 0) {
            IterT mid = first + std::distance(first, last) / 2;
            if (comp(*mid, target)) {
            first = m章鱼彩票网-二分查找及其变体id + 1;
            } else if (comp(target, *mid)) {
            last = mid;
            } else { // equal
            result = mid;
            break;
            }
            }
            return result;
            }

            这一完结有一些技巧值得说一说。

            首要,查找规模是由 first 和 last 构成的左闭右开区间。在编程中,坚持运用左闭右开区间,可以防止大多数索引越界的问题。这是个好习惯,值得一说。

            其次,这一完结以 mid = low + (high - low) / 2 的方法来确认减半点。与之相对,还有一种写法是 mid = (low + high) / 2。在数学的视点,这两种写法完全相同。但是在计算机的视点,后者或许涉及到整数的溢出。因而,为了防止溢出,咱们应当优先选用完结傍边的写法。

            最终,这一完结以 while 循环代替递归,节省了函数的递归调用带来的开支。与之调配,在未能找到方针时,经过调整区间首尾完结减半动作。这种完结方法是处于功率的考量。

            二分查找的变体

            单就查找等于方针的元素来说,这一使命还有哈希表和查找树等数据结构能高效地完结。相较二分查找,它们的约束更少——不需求数据集自身有序,也不需求分配接连的大块内存。如此看来,二分查找好像仅仅看起来夸姣,实践用处应该不广。

            但事实上,二分查找还有若干变体。这些变体完结的功用,上述这些数据结构一般很难以较低的时刻复杂度完结。这些变体才是最能体现二分查找威力的场景。这儿介绍常见的四个变体:

            • 查找支撑随机拜访的有序数据会集,第一个等于给定值的元素
            • 查找支撑随机拜访的有序数据会集,最终一个等于给定值的元素
            • 查找支撑随机拜访的有序数据会集,第一个不小于给定值的元素
            • 查找支撑随机拜访的有序数据会集,最终一个不大于给定值的元素

            这些变体的完结也不难。在上述规范二分查找的根底上,只需求稍加改造即可。需求重视的中心点,就是在不同条件下,区间的首尾应该怎么改变。以下是我以 C++ 完结的这些变体。这份完结里值得一提的当地,在根底款的二分查找完结中现已提过,便不再赘述。

            仿制

            #include 
            #include
            enum class BsearchPolicy { UNSPECIFIED, FIRST, LAST, FIRST_NOT_LESS, LAST_NOT_GREATER };
            template
            typename ValueT = typename std::iterator_traits::value_type,
            typename Compare>
            IterT bsearch(IterT first,
            IterT last,
            ValueT target,
            Compare comp,
            BsearchPolicy policy = BsearchPolicy::UNSPECIFIED) {
            IterT result = last;
            while (std::distance(first, last) > 0) {
            IterT mid = first + std::distance(first, last) / 2;
            if (policy章鱼彩票网-二分查找及其变体 == BsearchPolicy::FIRST_NOT_LESS) {
            if (!comp(*mid, target)) {
            if (mid == first or comp(*(mid - 1), target)) {
            result = mid;
            break;
            } else {
            last = mid;
            }
            } els章鱼彩票网-二分查找及其变体e {
            first = mid + 1;
            }
            } else if (policy == BsearchPolicy::LAST_NOT_GREATER) {
            if (comp(target, *mid)) {
            last = mid;
            } else {
            if (std::distance(mid, last) == 1 or comp(target, *(mid + 1))) {
            result = mid;
            break;
            } else {
            first = mid + 1;
            }
            }
            } else { // policy == UNSPECIFIED or FIRST or LAST
            if (comp(*mid, target)) {
            fir章鱼彩票网-二分查找及其变体st = mid + 1;
            } else if (comp(target, *mid)) {
            last绝对领域 = mid;
            } else { // equal
            if (policy == BsearchPolicy::FIRST) {
            if (mid == first or comp(*(mid - 1), *mid)) {
            result = mid;
            break;
            } else {
            last = mid;
            }
            } else if (policy == BsearchPolicy::LAST) {
            if (std::distance(mid, last) == 1 or comp(*mid, *(mid + 1))) {
            result = mid;
            break;
            } else {
            first = mid + 1;
            }
            } else {
            result = mid;
            break;
            }
            }
            }
            }
            return result;
            }
            template
            typename ValueT = typename std::iterator_traits::value_type,
            typename Compare = std::less>
            IterT bsearch(IterT first,
            IterT last,
            ValueT target,
            BsearchPolicy policy = BsearchPolicy::UNSPECIFIED) {
            return bsearch(first, last, target, Compare(), policy);
            }

            来历:Liam Huang / https://liam.page/2018/11/23/binary-search-and-its-variants/ ,只作共享,不作任何商业用处,版权归原作者一切

            请关注微信公众号
            微信二维码
            不容错过
            Powered By Z-BlogPHP