写在最前面，感谢Y总的板子~~~

本文来总结下二分查找思想。

它的核心思想： 性质的边界

模板1

先来看下示意图：

那么我们要求的答案有什么特点？

第一次满足某个性质

分为两种情况，当mid满足了这个性质：

说明什么？

答案在左边，且mid可能就是答案。

否则，答案在右边。

int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

模板2

老规矩：

我们要找的答案有什么特点？

最后一次满足某个性质。

也分为两种情况，如果mid满足这个性质：

说明什么？

答案在右边，或者mid就是答案。

否则，答案在左边。

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;
}

注意+1的目的，是防止向下取整，最终导致死循环。

实战

• *1、[69] Sqrt(x){:target=”_blank”}
• 2、[367] Valid Perfect Square{:target=”_blank”}
• 3、[540] Single Element in a Sorted Array{:target=”_blank”}
• 4、[278] First Bad Version{:target=”_blank”}
• 5、[153] Find Minimum in Rotated Sorted Array{:target=”_blank”}
• 6、[154] Find Minimum in Rotated Sorted Array II{:target=”_blank”}
• 7、[33] Search in Rotated Sorted Array{:target=”_blank”}
• 8、[81] Search in Rotated Sorted Array II{:target=”_blank”}
• 9、[34] Find First and Last Position of Element in Sorted Array{:target=”_blank”}
• 10、[74] Search a 2D Matrix{:target=”_blank”}
• 11、[162] Find Peak Element{:target=”_blank”}
• 12、[852] Peak Index in a Mountain Array{:target=”_blank”}
• 13、[35] Search Insert Position{:target=”_blank”}