这篇文章主要介绍“java二分查找怎么实现迭代”的相关知识,小编通过实际案例向大家展示操作过程,操作方法简单快捷,实用性强,希望这篇“java二分查找怎么实现迭代”文章能帮助大家解决问题。
1.迭代概念
对一组指令或一定步骤进行重复执行称为迭代(iterator)。通俗点说,叫一个个数过去。
实现这样一个个数过去功能的东西,叫迭代器。
2.迭代三要素
1.确定变量
在可以用迭代算法解决的问题中,至少存在一个直接或间接地不断由旧值递推出新值的变量,这个变量就是迭代变量。
2.建立关系式
所谓迭代关系式,指如何从变量的前一个值推出其下一个值的公式(或关系)。迭代关系式的建立是解决迭代问题的关键,通常可以使用递推或倒推的方法来完成。
3.过程控制
在什么时候结束迭代过程?这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况:一种是所需的迭代次数是个确定的值,可以计算出来;另一种是所需的迭代次数无法确定。对于前一种情况,可以构建一个固定次数的循环来实现对迭代过程的控制;对于后一种情况,需要进一步分析出用来结束迭代过程的条件。
3.二分查找的迭代实例
/*非递归的折半查找*/ public static int binarySearch(int[] a, int x) { int left = 0; int right = a.length - 1; while(left <= right) { int mid = (left+ right) / 2; if(x > a[mid]) { left = mid+1; } else if(x < a[mid]) { right = mid-1; } else { return mid; } } return -1; }
每次迭代在循环内的所有工作话费O(1),因此分析需要确定循环的次数。循环从right-left=leng-1开始并在right-left<= -1结束。每次循环后right-left的值至少将该循环前的值折半;于是,循环的次数最多是[log(n-1)]+2。因此:运行的时间是O(log N),而递归的时间复杂度则需要O(N)。
关于“java二分查找怎么实现迭代”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识,可以关注亿速云行业资讯频道,小编每天都会为大家更新不同的知识点。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。