二分查找算法模板

binary search template

• 简单好用的二分查找算法模板，最好能够背下来。
• 二分查找法的思想1946年提出，但第一个没有bug的二分查找法1962年才出现。可见看似简单的二分查找算法，代码实现也不是一件容易的事情。
• 普通人很难发明出这类经典算法，写不出来，也不要气馁，只要能够掌握就已经可以了。
• 二分查找时间复杂度 O(logn) 性能非常好, 但前提条件是数据集合是要有序的。

// template 1
while(l < r){
    mid = (l + r) / 2
    if(check(mid))  // func(mid, x) { return mid >= x }
        r = mid // 看到 r = mid 应该想到的是 下一次查找范围在左边 [l, mid]
    else 
        l = mid + 1 // 否则 [mid+1, r] 下一次查找去右边找
}

// template 2
while(l < r){
    mid = (l + r + 1) / 2
    if(check(mid)) // func(mid ,x) { return mid <= x }
        l = mid     // [mid, r] 这个就表示下一次要去右边查找， 因此要 + 1
    else
        r = mid - 1 // [l, mid - 1]
}