二分法模板

很大一部分借鉴于这里

查找大于等于/大于key的第一个元素

这种通常题目描述为满足某种情况的最小的元素。

    int left = 1,right = n;
    while(left < right)
    {
        //这里不需要加1。我们考虑如下的情况，最后只剩下A[i],A[i + 1]。
        //首先mid = i，如果A[mid] > key，那么right = left = i，跳出循环，如果A[mid] < key，left = right = i + 1跳出循环，所有不会死循环。
        int mid = (left + right) / 2;
        if(A[mid] > key)//如果要求大于等于可以加上等于，也可以是check(A[mid])
            right = mid;
        //因为找的是大于key的第一个元素，那么比A[mid]大的元素肯定不是第一个大于key的元素，因为A[mid]已经大于key了，所以把mid+1到后面的排除
        else
            left = mid + 1;
        //如果A[mid]小于key的话，那么A[mid]以及比A[mid]小的数都需要排除，因为他们都小于key。不可能是第一个大于等于key的元素，
    }

三、查找小于等于/小于key的最后一个元素

这种通常题目描述为满足某种情况的最大的元素。如Leetcode69题，求sqrt(x)向下取整就是这种模板。

    int left = 1, right = n;
    while(left < right)
    {
        //这里mid = (left + right + 1) / 2;
        //考虑如下一种情况，最后只剩下A[i],A[i + 1]，如果不加1，那么mid = i，如果A[mid] < key，执行更新操作后，left = mid，right = mid + 1，就会是死循环。
        //加上1后，mid = i + 1,如果A[mid] < key，那么left = right = mid + 1,跳出循环。如果A[mid] > key，left = mid = i，跳出循环。
        int mid = (left + right + 1) / 2;
        if(A[mid] < key)
            left = mid;//如果A[mid]小于key，说明比A[mid]更小的数肯定不是小于key的最大的元素了，所以要排除mid之前的所有元素
        else
            right = mid - 1;//如果A[mid]大于key，那么说明A[mid]以及比A[mid]还要大的数都不可能小于key，所以排除A[mid]及其之后的元素。
    }