经典算法之右边界二分查找法(俗称基本右边界二分搜索法)
2021/11/21 14:10:35
本文主要是介绍经典算法之右边界二分查找法(俗称基本右边界二分搜索法),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
经典算法之右边界二分查找法(俗称基本右边界二分搜索法)
提示:写完文章后,目录可以自动生成,如何生成可参考右边的帮助文档
文章目录
- 经典算法之右边界二分查找法(俗称基本右边界二分搜索法)
- 前言
- 一、什么是右边界二分查找法?
- 二、代码实现
- 总结
前言
就算法而言,我们主要学习的是数学+思维+逻辑+数据结构实现功能,所以我们主要学习是思维也是解决问题的思路,然后用逻辑去实现它。
提示:以下是本篇文章正文内容,下面案例可供参考
一、什么是右边界二分查找法?
寻找右侧边界和寻找左侧边界的代码差不多,不痛点在与当起始位+截止位的和右移之后数组下角标对应的数组值等于要查询额参数值要+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时做修改即可。搜索右侧时需要减一。
这篇关于经典算法之右边界二分查找法(俗称基本右边界二分搜索法)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南
- 2024-09-30Dnd-Kit学习:新手快速入门指南