这次我敢打包票我是真的 ~~完全~~ 进了一大步了解了二分。

这个内容对在座的各位大佬来说肯定还是很简单的,菜鸡现在才搞懂,个人还是觉得是有里程碑的意义的。

1.元素完全确定的二分查找

这是二分查找的最简单形式,就是你要查找的值确定,且不重复。
这种形式下,只要找到这个值直接返回即可。

int binarySearch(int le, int ri, int val)
{
    int mid;
    while (le <= ri) {
        mid = (le + ri) >> 1;
        if (ary[mid] == val)
            return mid;
        else if (ary[mid] > val)
            ri = mid - 1;
        else
            le = mid + 1;
    }
    return -1;
}

2.给定条件的二分查找

举个栗子,求出某个有序序列中最小的比val大的数,第一个等于val的下标等等……

这种二分查找当我们找到一个满足约束条件的值时,我们就尝试着去扩大这个约束极限,使得它更满足我们的条件。我这里可能表述不清楚,比如 ary[idx] > val ,假设序列递增 , 那么可以尝试让idx向右移动。

而对于初学者来说,可能会有两个很困惑的地方。

2.1 最后的二分的结果究竟 取 l ? r ?

当然如果是浮点数二分的话,直接返回 mid 即可

曾经我拿这个问题去问学长,学长说看情况,所以我拖到了现在。
其实我用一句话概括的话,==就是你最后一个满足条件的 mid ==。

我这里举个栗子,查找某个递增序列中最小的比val大的数。

int binarySearch(int le, int ri, int val)
{
    int mid, rlen = ri + 1;
    while (le <= ri) {
        mid = (le + ri) >> 1;
        if (ary[mid] > val) //此时的ary[mid] 满足约束条件
            ri = mid - 1;
        else
            le = mid + 1;
    }
    return ri == rlen ? -1 : ary[ri + 1]; //若val比ary[0]还小,那么ary[0]是满足要求的。
                                          //但如果数组中不存在比val大的数,就要特判一下。
                                          // mid = ri+1 就是在二分过程中最后一个满足约束条件的 idx
}
2.2 在while循环的时候,\( le \le ri \) 还是 \(le \lt ri\)

首先我们可以确定的是,在浮点数二分的时候,这个等于并不会给我们带来太大影响。
而不管是浮点数还是整型数,加了一个等于都能是我们进一步扩大极限的机会。

哦,说白了,其实这个我也不是很清楚,你只要把 = 加上去肯定是没错的……

这个坑以后回来再填。

Categories: 二分

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Related Posts

二分

我也不是B(倍增二分

玲珑杯 Round #13 B题 DESCRIPTION 小 L 有一 Read more…

二分

HDU 4355 Party All the Time

暑假集训选拔马上就要开始了 挺虚的,就临时抱一下佛脚 把以前没有写的周 Read more…