
二分查找(递归)
问题分析:由于数组是排好序的,二分查找是一个高效的选择。我们需要找到第一个大于给定数字的位置。 递归设计:递归方法需要传入数组、起始位置、结束位置和目标数字。中间位置的计算是关键,根据目标数字的大小决定搜索方向。 终止条件:当起始位置和结束位置相邻时,比较目标数字和当前位置的值,决定返回起始位置还是结束位置。 主函数:调用 初始检查:如果目标数字大于或等于数组的最大值,直接返回-1。 递归方法:计算中间位置,根据目标数字的大小决定搜索方向。终止条件是起始位置和结束位置相邻,比较目标数字和当前位置的值,返回合适的位置。
发布日期:2021-05-07 22:03:35
浏览次数:11
分类:精选文章
本文共 1077 字,大约阅读时间需要 3 分钟。
为了解决这个问题,我们需要找到一个排好序的整型数组中比给定数字稍微大一点的那个位置。如果没有找到这样的位置,则返回-1。我们将使用二分查找来高效地解决这个问题。
方法思路
解决代码
public class Main { public static void main(String[] args) { int arr[] = {1, 5, 11, 24, 25, 32, 32, 32, 33}; System.out.println(solve(arr, 32)); } public static int solve(int arr[], int x) { if (x >= arr[arr.length - 1]) return -1; return solve(arr, 0, arr.length - 1, x); } private static int solve(int[] arr, int begin, int end, int x) { if (end - begin == 1) { if (arr[begin] > x) return begin; return end; } int k = (begin + end) / 2; if (x >= arr[k]) return solve(arr, k, end, x); return solve(arr, begin, k, x); }}
代码解释
solve
方法,传入数组和目标数字。这个方法利用了二分查找的高效性,确保在O(log n)时间复杂度内找到目标位置。
发表评论
最新留言
不错!
[***.144.177.141]2025年04月11日 03时55分10秒
关于作者

喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
windows环境利用start命令实现微信多开
2019-03-04
「CF149D」括号涂色 区间DP好题
2019-03-04
树状数组 模板总结
2019-03-04
「NOI2015」程序自动分析 并查集题解
2019-03-04
[JSOI2008]Blue Mary的战役地图 Hash题解
2019-03-04
结构型设计在工作中的一些经验总结
2019-03-04
如何提升员工体验 助力企业业务增长?这个棘手的问题终于被解决了!
2019-03-04
2020 AI 产业图谱启动,勾勒中国 AI 技术与行业生态
2019-03-04
“编程能力差,90%输在了数学上!”CTO:多数程序员都是瞎努力!
2019-03-04
YbtOJ hash和hash表课堂过关 例1 字符串哈希【hash】
2019-03-04
前后端数据交互之表单
2019-03-04
剑指offer JZ21 栈的压入弹出序列
2019-03-04
Netty4服务端入门代码示例
2019-03-04
VL53L0x TOF激光测距的 stm32 HAL库驱动代码
2019-03-04
自定义标签(JSP2.0)简单标签
2019-03-04
MyBatis自定义类型转换器
2019-03-04
Python:函数 ----》装饰器函数
2019-03-04
Python:面向对象
2019-03-04
Spring源码:prepareBeanFactory(beanFactory);方法
2019-03-04
Spring源码:initApplicationEventMulticaster源码解析
2019-03-04