java两种实现二分查找方式
JAVA 实现 方式 查找 两种 二分
2023-09-14 09:07:47 时间
二分查找法适用于 升序排列的数组,如果你所要操作的数组不是升序排序的,那么请用排序算法,排序一下。
说明:使用二分查找法相比顺序查找 节约了时间的开销,但是增加了空间使用。因为需要动态记录 起始索引和结束索引和中间索引。
顺序查找 平均和最坏情况时间复杂度 :O(n)
二分查找法 时间复杂度 为 :O(log2n)
package part1; /** * Created by Administrator on 2018/7/31. */ public class demo01{ /* * 循环实现二分查找算法arr 已排好序的数组x 需要查找的数-1 无法查到数据 */ /** * * @param arr 数组对象 * @param x 所要查找的数 * @return */ public static int binarySearch(int[] arr, int x) { int low = 0; int high = arr.length-1; while(low <= high) { int middle = (low + high)/2; //取中间索引 if(x == arr[middle]) { return middle; }else if(x <arr[middle]) { high = middle - 1; //如果所找的的数小于中间索引对应的值证明所要找的数在左半边,将中间索引前一位设置为终点索引 }else { low = middle + 1; //如果所找的的数大于中间索引对应的值证明所要找的数在右半边,将中间索引后一位设置为开始索引 } } return -1; } //递归实现二分查找 /** * * @param dataset 数组对象 * @param data 所要查找的数 * @param beginIndex 开始索引 * @param endIndex 结束索引 * @return */ public static int binarySearch(int[] dataset,int data,int beginIndex,int endIndex){ int midIndex = (beginIndex+endIndex)/2; //取中间索引 //如果查找的数小于第一位数 或者 查找的数大于最后一位数 或者 起始索引大于结束索引 都说明所查找的数不存在 if(data <dataset[beginIndex]||data>dataset[endIndex]||beginIndex>endIndex){ return -1; } //如果查找的数小于中间索引对应的值说明找的数在左半边,递归调用该查找方法,结束索引为中间索引向左移动一位 if(data <dataset[midIndex]){ return binarySearch(dataset,data,beginIndex,midIndex-1); //如果查找的数大于于中间索引对应的值说明找的数在右半边,递归调用该查找方法,起始索引为中间索引向右移动一位 }else if(data>dataset[midIndex]){ return binarySearch(dataset,data,midIndex+1,endIndex); //如果所查找的数正好等于中间索引对应的值,那么就将该索引返回 }else { return midIndex; } } public static void main(String[] args) { int[] arr = { 11,22,33,44,55,66,77,88}; System.out.println("循环查找:" + (binarySearch(arr, 44) + 1)); System.out.println("递归查找"+(binarySearch(arr,44,0,arr.length-1)+1)); } }
相关文章
- 深入Java线程管理(一):线程的实现方式
- Java实现 LeetCode 778 水位上升的泳池中游泳(二分+DFS)
- Java实现 蓝桥杯 算法训练 求和求平均值
- Java实现 LeetCode 728 自除数(暴力)
- Java实现 LeetCode 515 在每个树行中找最大值
- Java实现 LeetCode 507 完美数
- Java实现 LeetCode 395 至少有K个重复字符的最长子串
- Java实现 LeetCode 350 两个数组的交集 II(二)
- Java实现蓝桥杯VIP算法训练 二元函数
- Java实现蓝桥杯VIP算法训练 相邻字母
- Java实现 LeetCode 223 矩形面积
- Java实现 LeetCode 104 二叉树的最大深度
- Java实现 洛谷 P1200 [USACO1.1]你的飞碟在这儿Your Ride Is He…
- Java实现交替字符串
- Java实现台阶问题
- Java实现约瑟夫环问题
- Java实现 蓝桥杯VIP 算法提高 计算时间
- Java实现 蓝桥杯VIP 算法提高 解二元一次方程组
- Java实现 蓝桥杯VIP 算法训练 矩阵加法
- (Java实现)洛谷 P2095 营养膳食
- java核心知识点学习----多线程间的数据共享的几种实现方式比较
- java多线程 -- 创建线程的第三者方式 实现Callable接口
- 用JAVA的抽象类实现编码组合进度的灵活性
- aspose.slides for java去除水印
- 【学亮说】Java实现单例模式的8种方式(你真的搞懂单例模式了吗?)
- Java实现字符串反转的四种方式代码示例
- paip.提高效率---集合的存取括号方式 uapi java python php js 的实现比较
- paip.提高效率---集合的存取括号方式 uapi java python php js 的实现比较
- 关于省,市,区联动 java 实现方式
- Java 多线程实现的四种方式
- 基于JAVA实现的WEB端UI自动化 - WebDriver高级篇 - WebDriver的三种等待方式
- java对象和json数据转换实现方式3-使用jackson实现
- Java 实现标准输入的几种方式