Java实现二分查找算法(非递归)
2021/10/12 9:14:09
本文主要是介绍Java实现二分查找算法(非递归),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
14.1 二分查找算法(非递归)
14.1.1 二分查找算法(非递归)介绍
- 之前发过二分查找算法,是使用递归的方式,下面我们用二分查找算法的非递归方式
- 二分查找法只适用于从有序的数列中进行查找(比如数字和字母等),将数列排序后再进行查找
- 二分查找法的运行时间为对数时间 O(㏒₂n) ,即查找到需要的目标位置最多只需要㏒₂n 步,假设从[0,99]的队列(100 个数,即 n=100)中寻到目标数 30,则需要查找步数为㏒₂100 , 即最多需要查找 7 次( 2^6 < 100 < 2^7)
14.1.2 二分查找算法(非递归)代码实现
数组 {1,3, 8, 10, 11, 67, 100}, 编程实现二分查找, 要求使用非递归的方式完成。
代码实现
/** * @author zk * @version 1.0.0 * @ClassName BinarySearchNoRecur.java * @Description TODO 二分查找算法(非递归) * @createTime 2021年09月29日 14:52:00 */ public class BinarySearchNoRecur { public static void main(String[] args) { //测试 int[] arr = {1,3, 8, 10, 11, 67, 100}; int i = binarySearch(arr, 67); System.out.println(i); } //二分查找的非递归实现 /** * * @param arr 待查找的数组, arr 是升序排序 * @param target 需要查找的数 * @return 返回对应下标,-1 表示没有找到 */ public static int binarySearch(int[] arr,int target){ int left = 0; int right = arr.length-1; while (left<=right){ int mid = (left+right)/2; if (arr[mid]==target){ return mid; }else if (arr[mid]<target){ left = mid + 1; }else{ right = mid - 1; } } return -1; } }
如果想看Java实现二分查找算法(采用递归方式)的代码请查看之前文章,点击前往【Java实现二分查找算法(递归)】
这篇关于Java实现二分查找算法(非递归)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-06小米11i印度快充版ROM合集:极致体验,超越期待
- 2024-10-06【ROM下载】小米11i 5G 印度版系统, 疾速跃迁,定义新速度
- 2024-10-06【ROM下载】小米 11 青春活力版,青春无极限,活力全开
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 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 实现数据请求