/**
*
* @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]<searchKey){
lowerBound=curIn+1;
}
else{
upperBound=curIn-1;
}
}
}
}
public void insert(long value){
int j;
for(j=0; j<nElems; j++)
if(a[j]>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<nElems; j++){
System.out.println(a[j]+"");
}
}
}
class BinarySearchApp{
public static void main(String[] args){
int maxSize=100;
OrdArray arr=new OrdArray(maxSize);
arr.insert(72);
arr.insert(90);
arr.insert(45);
arr.insert(126);
arr.insert(54);
arr.insert(99);
arr.insert(144);
arr.insert(27);
arr.insert(135);
arr.insert(81);
arr.insert(18);
arr.insert(100);
arr.insert(9);
arr.insert(117);
arr.insert(63);
arr.insert(36);
arr.display();
int searchKey=100;
if(arr.find(searchKey) !=arr.size())
System.out.println("Found "+searchKey);
else
System.out.println("Can't find "+ searchKey);
}
}
/**
* 运行结果:
* 9
* 18
* 27
* 36
* 45
* 54
* 63
* 72
* 81
* 90
* 99
* 100
* 117
* 126
* 135
* 144
* Found 100
*/
/**
* 总结:
* 很多的数学问题都使用递归的方法解决,比如找两个数的最大公约数,求一个数的
* 乘方等等。如果有效率需求的时候,可以再考虑将递归转化成非递归。
*/
分享到:
相关推荐
折半查找(二分查找)折半查找(二分查找)折半查找(二分查找)折半查找(二分查找)折半查找(二分查找)折半查找(二分查找)
二分查找算法,二分查找算法课件,二分查找算法PPT
二分查找_测试
二分查找算法
简单地实现了二分查找的可视化。界面很简单就包括两个部分:界面左侧是可视化查找部分,右侧是二分查找的代码。 程序的关键点主要有两点: 1. 如何在页面上表示出查找程序的运行过程。 2. 如何将排序程序的运行...
1.二分查找又称为折半查找,它要求要查找的顺序表必须是有序表,即表中结点按关键字有序.并且要用顺序存储结构。 基本思想是:首先将给定值key与表中中间位置记录的关键字相比较,若二者相等,则查找成功,否则...
二分查找 C语言语言源代码 用递归写的 C语言入门经典代码 值得收藏
//二分查找 #include const int MAXN=10010; using namespace std; //二分查找,递归实现 int binarySearch(int a[],int low,int high,int key) { //查找某元素是否在数组中,若存在,则返回下标,否则...
二分查找
二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。首先,假设表中元素是按升序排列,将表...
二分查找
VB 二分查找 VB 二分查找 VB 二分查找
s[middle] 关键字小于中值 继续二分查找 并将上限改为middle BinarySearch s x low middle 1 ; else 关键字大于中值 继续二分查找 并将下限改为middle BinarySearch s x middle + 1 high ;">if high < low ...
二分查找ppt
一、实验目的: 熟悉各种查找算法及其复杂性,能够根据实际情况选择合适的存储结构。 二、实验要求: 1、掌握查找的基本方法。 2、提交实验报告,报告...编程分别对有序顺序表的顺序查找,二分查找算法进行实现。
int BinSearch(SeqList R,int n,KeyType k) /*二分查找算法*/ { int low=0,high=n-1,mid,count=0; while (low) { mid=(low+high)/2; printf("第%d次查找:在[%d,%d]中查找到元素R[%d]:%d\n",++count,low,high,...
文件读出数组进行选择排序和二分查找文件读出数组进行选择排序和二分查找java实现
设计一个程序,建立由有序序列R[0..n-1]进行二分查找产生的判定树,在此基础上完成如下功能: (1) 输出n=11时的判定树并求成功情况下的平均查找长度ASl (2) 通过构造判定树可以求得的成功情况下的平均查找长度...
C++ 二分查找法