技术文章 > java >  java基础 > 正文

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二分查找实现迭代的方法,建议大家对迭代和二分查找的基础知识点掌握牢固后,在进行二者的结合使用。有概念模糊的地方,可以在课后查找有关资料。

免费视频教程
本教程部分素材来源于网络,版权问题联系站长!
相关文章
  Java中反射机制是什么?
  java反射方式创建实例
  java反射原理简单介绍
  java反射面试题有哪些
  java字符串转换数组的两种方式
  Java中的Arrays类是什么
  Java Arrays类的常见使用
  java代理模式的分类
  java中使用toString打印数组
  java数组中有哪些面试题
相关视频章节
  索引和切片(上)
  数组创建和属性
  Python数据分析常用库
  高级函数(下
  高级函数(上)
作者信息
推荐视频
视频教程分类