二分查找入门、二分查找模板

二分查找的具体实现是一个难点，挺复杂的，可以背住一个模板，然后以后再慢慢学习。下面是y总的二分模板(比较难懂，之后再学)

y总的模板

二分的本质是在一个边界内，定义了两种不同的形状，其中某点是这两个性质的分割处。而在顺序数组二分查找值：就是在target点左边点的性质是[0,target]内的点都小于等于target，而在右边的点都大于等于target。而点tar是满足左右性质的唯一点。

–y总的模板有个特点（bsearch_1），就是当查找命中时，并不是直接返回，而是将结果保存在左指针，然后继续进行查找，直至双指针相等自动停止。（y总二分实际是左闭右开的一种特殊写法，比较简洁的那种）

在这里插入图片描述

bsearch_1是绿色的情况（返回从左数最小的满足check的元素下标），bsearch_2是红色的情况

！~~注意：yxc二分模板r=length-1，要注意上下限问题

bool check(int x) {/* ... */} // 检查x是否满足某种性质
//返回tar或大于tar的数中最小的那个的下标  //如果未命中，返回从左数最小的满足check的元素下标
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足右性质，如果满足右性质，就往左移动
        else l = mid + 1;		   // 不满足右性质，满足左性质，往右移动，但mid没命中，被淘汰，所以mid+1
    }
    return l;
}
//约等于如下写法
        int l = 0, r = nums.length-1;
        while (l < r){
            int mid = l + r >> 1;
            if (nums[mid] - target == 0) return mid;
            else if (nums[mid] - target > 0) r = mid;
            else l = mid + 1;
        }
        return l;

//返回tar或小于tar的数中最大的那个的下标  //如果未命中，返回从右数最大的满足check的元素下标
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;			// 如果命中tar想要缩短左边界，就这样写（int m = l + (r-l+1)/2 ;）
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}
// 如果不存在点tar，bsearch_2命中右性质最小，bsearch_1命中左性质最大
作者：yxc
链接：https://www.acwing.com/blog/content/277/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

做法：

如果判断该题是用二分，直接上来先把模板写好，然后写好check函数，然后用特例判断一下边界问题，看一下是用上面你的模板还是下面的模板；至于模板的原理，没必要细究。

    public int searchInsert(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        if (nums[r] < target) return r + 1;
        while (l < r){
            int mid = l + r >> 1;
            if (check(nums, mid, target)) r = mid;
            else l = mid + 1;
        }
        return l;
    }
    boolean check(int[] nums, int mid, int target){
        //tar前,[i]-[tar] < 0 --性质1
        //tar后,[i]-[tar] > 0 --性质2
        //tar时,[i]-[tar] = 0 --性质3

        //将此代码简写
        /*
        if (nums[mid] >= target){//命中性质2、3时
            return true;
        }else{
            return false;
        }
        */
        return nums[mid] >= target;
    }

    public int searchInsert(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        if (nums[r] < target) return r + 1;
        while (l < r){
            int mid = l + r >> 1;
            if (check()) r = mid;//命中性质2、3时
            else l = mid + 1;
        }
        return l;
    }
    boolean check(){
        //tar前,xxxxx --性质1
        //tar后,xxxxx --性质2
        //tar时,xxxxx --性质3
        
        //将此代码简写
        if (性质判定){//命中性质2、3时
            return true;
        }else{
            return false;
        }
    }