经典算法之右边界二分查找法(俗称基本右边界二分搜索法)

文章目录

• 经典算法之右边界二分查找法(俗称基本右边界二分搜索法)
• 前言
• 一、什么是右边界二分查找法？
• 二、代码实现
• 总结

前言

就算法而言，我们主要学习的是数学+思维+逻辑+数据结构实现功能，所以我们主要学习是思维也是解决问题的思路，然后用逻辑去实现它。

提示：以下是本篇文章正文内容，下面案例可供参考

一、什么是右边界二分查找法？

寻找右侧边界和寻找左侧边界的代码差不多，不痛点在与当起始位+截止位的和右移之后数组下角标对应的数组值等于要查询额参数值要+1，起始位>截止位要 -1（左边法参考我的算法左边界搜索法文章）。

二、代码实现

package com.zrrd.lianxi;

public class 二分查找法 {

    public static void main(String[] args) {
        int a[]={1,2,3,4,5,6,7,8,9,10};
        int i2 = rightErFenFaQuery(a,5);
        System.out.println("返回的索引位为"+i2);

    }
    /**
     * 寻找右侧边界的二分查找
     */
    public static int rightErFenFaQuery(int[] shuzu, int cs) {
        //校验数组大小
        if (shuzu.length == 0)
            return -1;
        //定义查询范围起始下角标
        int start = 0;
        //定义查询范围截止下角标
        int end = shuzu.length;

        while (start < end) {
            /**将查询范围起始位+截止位之和  无符号右移 1 位
             *  >>>  运算符详解：无符号右移：低位抛弃，高位补0.
             *  以上举例：0 + 2 = 2      2 >>> 1
             *  数字2的二进制吗      0000 0010
             *  右移之后的二进制码   0000 0001     （是数字1）
             **/
            int laf = (start + end) >>> 1;
            if (shuzu[laf] == cs) {
                start = laf + 1;
                //判断当前数组值 是否 小于查询的参数
            } else if (shuzu[laf] < cs) {
                //小于则下角标+1
                start = laf + 1;
                //判断当前数组值 是否 大于查询的参数
            } else if (shuzu[laf] > cs) {
                end = laf;
            }
        }
        //搜索右侧时需要减一
        return start - 1;
    }
}

效果截图：

结构图仅供参考：

总结

注意「搜索区间」和 while 的终止条件，如果存在漏掉的元素，记得在最后检查，.如需要搜索左右边界，只要在 shuzu[laf] == cs时做修改即可。搜索右侧时需要减一。