文件名称:
数据结构与算法（JAVA篇）之递归算法（二）
开发工具:
文件大小: 4kb
下载次数: 0
上传时间: 2008-11-26
详细说明： /** * * @author SunnyMoon */ /** * 概念介绍: * * 递归的二分查找: 想用最少的比较次数在一个有序的数组中找到一个给定的数据项。 * * 非递归的二分查找：二分查找也可以用非递归的算法，但是分治算法通常要回到递归。分治算 * 法常常是一个方法，在这个方法中含有两个对自身的递归的调用。 * * 分治算法：递归的二分查找是分治算法的一种实现方法。把一个是问题分成两个更小的问题， * 并且解决它们。这个过程一直持续下去直到易于求解的基值情况，就不需再分了。 * 分治算法常常是一上方法，在这个方法中含有两个对自身的递归调用，分别对应于 * 问题的两个部分。在二分查找中，就有两个这样的调用，但是只有一个真的执行了 * （调用哪一个取决于关键字的值）。 * 递归的效率：调用一个方法会有一定的代价和开销。首先，控制必须须从当前位置转移到调用 * 方法的开始处。其次，传给这 个方法的参数以及这个方法返回地址都要初压到一 * 个栈里，为的是方法能够访问参数以及知道返回值在存储在哪里，这个过程也称 * "保存现场"。递归方法的使用的本质是从概念上简化了问题，而不是因为它更有 * 效率。当使用递归的效率很低的时候，就可以考虑如果把递归转化成非递归。 */ class OrdArray { private long[] a; private int nElems; public OrdArray(int max) { a = new long[max]; nElems = 0; } public int size() { return nElems; } public int find(long searchKey) { return recFind(searchKey, 0, nElems - 1);//调用递归方法 //return recFind2(searchKey, 0, nElems - 1);//调用非递归方法 } public int recFind(long searchKey, int lowerBound, int upperBound) {//递归方法定义 int curIn = (lowerBound + upperBound) / 2; if (a[curIn] == searchKey) { return curIn; } else if (lowerBound > upperBound) { return nElems; } else { if (a[curIn] < searchKey) { return recFind(searchKey, curIn + 1, upperBound); } else { return recFind(searchKey, lowerBound, curIn - 1); } } } public int recFind2(long searchKey, int lowerBound, int upperBound){//非递归方法定义 int curIn=0; while(true){ curIn=(lowerBound+upperBound)/2; if(a[curIn]==searchKey) return curIn; else if(lowerBound>upperBound) return nElems; else{ if(a[curIn]value) break; for(int k=nElems; k>j; k--) a[k]=a[k-1]; a[j]=value; nElems++; } public void display(){ for(int j=0; j
(系统自动生成,下载前可以参看下载内容)
下载文件列表
相关说明
- 本站资源为会员上传分享交流与学习,如有侵犯您的权益,请联系我们删除.
- 本站是交换下载平台，提供交流渠道，下载内容来自于网络，除下载问题外，其它问题请自行百度。
- 本站已设置防盗链，请勿用迅雷、QQ旋风等多线程下载软件下载资源，下载后用WinRAR最新版进行解压.
- 如果您发现内容无法下载，请稍后再次尝试；或者到消费记录里找到下载记录反馈给我们.
- 下载后发现下载的内容跟说明不相乎，请到消费记录里找到下载记录反馈给我们，经确认后退回积分.
- 如下载前有疑问，可以通过点击"提供者"的名字，查看对方的联系方式，联系对方咨询.
