编程知识 cdmana.com

ACM algorithm competition - integer bisection algorithm (template)

Integer bisection is used to quickly find the location of a value , Order must be dichotomous , The conditions of dichotomy are not necessarily orderly , But it's generally orderly

bool check(int x) {/* ... */} //  Check x Whether it satisfies certain properties //  Section [l, r] Divided into [l, mid] and [mid + 1, r] When using :int bsearch_1(int l, int r){    while (l < r)    {        int mid = l + r >> 1;        if (check(mid)) r = mid;    // check() Judge mid Is the property satisfied         else l = mid + 1;    }    return l;}//  Section [l, r] Divided into [l, mid - 1] and [mid, r] When using :int bsearch_2(int l, int r){    while (l < r)    {        int mid = l + r + 1 >> 1;        if (check(mid)) l = mid;        else r = mid - 1;    }    return l;}

版权声明
本文为[Hua Weiyun]所创,转载请带上原文链接,感谢
https://cdmana.com/2022/134/202205141315108789.html

Scroll to Top