public class biSearch {
/**
* @param args
* 作者:undoner
/*
折半查找--当查找表是有序表时,可采用折半查找;
基本思想:在有序表中,取中间元素作为比较对象,若给定值K与中间记录关键字相等,则查找成功;
若给定值K小于中间记录的关键字,则在表的左半区继续查找;
若给定值K大于中间记录的关键字,则在表的右半区继续查找,不断重复,直到查找成功/失败。
*/
//折半查找非递归算法
//查询成功返回该对象的下标序号,失败时返回-1。
int BiSearch(int r[],int n,int k)
{
int low=0;
int high=n-1;
while(low<=high)
{
int mid=(low+high)/2;
if(r[mid]==k)
return mid;
else
if(r[mid]<k)
low=mid+1;
else
high=mid-1;
}
return -1;
}
//折半查找递归算法
//查询成功返回该对象的下标序号,失败时返回-1。
int BiSearch2(int r[],int low,int high,int k)
{
if(low<0) low=0;
if(high>=r.length) high=r.length-1; //简单的参数验证
if(low>high)
return -1;
else
{
int mid=(low+high)/2;
if(r[mid]==k)
return mid;
else
if(r[mid]<k)
return BiSearch2(r,mid+1,high,k);
else
return BiSearch2(r,low,mid-1,k);
}
}
public static void main(String[] args) {
biSearch bs=new biSearch();
int r[]={1,2,3,4,5};
System.out.println(bs.BiSearch(r,5,5));
System.out.println(bs.BiSearch2(r,0,4,5));
System.out.println(bs.BiSearch2(r,0,5,5));
}
}
运行:
C:\java>java biSearch
4
4
4
分享到:
相关推荐
非递归查找的简单C语言程序,供初学者参考一下,哈哈。
用C语言开发的递归和非递归二分查找算法,具体内容详见代码
分别用递归和非递归方法实现二分查找算法 的完整程序,indexof()返回的是循环实现的二分法查找,getindex()实现的是递归算法实现的二分法查找。
C语言数据结构实验,在算法设计初级阶段也可以用到,入门级分享
请写出对有序表进行折半查找的非递归算法.doc
这里本人自己写的是折半查找算法(又称二分查找)的c++代码的实现, 用的是递归的方法和非递归的方法, 里面的代码已经编译通过,并且优化好, 有需要的朋友可以下载借鉴一下
第1题:选择合适的存储结构,读取已知文件数据建立查找表,将表内数据有序化,并完成基于递归和非逆归的折半查找算法的设计。 第2题:完成基于区间约束对折半查找算法的改进算法的设计。 第3题:完成三分查找算法...
主要介绍了PHP实现的折半查找算法,简单描述了折半查找的原理,并结合实例形式分析了php采用递归与非递归方式实现折半查找算法的相关操作技巧,需要的朋友可以参考下
虽然讲师的表述并不完美,但却不失为一个好的学习资料
实现一个学生管理系统,即定义一个包含学生信息(学号,姓名,成绩)的顺序表,可以不考虑重名的情况,系统包含以下功能: ...(9) 根据学号进行折半查找,要求使用非递归算法实现,成功返回此学生的姓名和成绩。
二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。首先,假设表中元素是按升序排列,将表...
选择一种合适排序算法排序,排序后对线性表采用折半查找(递归和非递归)。 3.实现直接插入排序、快速排序、归并排序算法。 4.设计一个程序,任意给出n个学生信息(包括:学号,姓名,成绩等),实现按照分数高低...
新翔教师学生信息综合管理系统 v3.0
-邻接矩阵.cpp 回文判断--队列.cpp 回文判断--栈.cpp 树的遍历--递归算法.cpp 树的遍历--非递归算法(先序).cpp 树的遍历--非递归算法(中序).cpp 约瑟夫环--链表.cpp 约瑟夫环--数组.cpp 折半查找--递归.CPP ......
主要介绍了PHP实现的折半查询算法,结合完整实例形式分析了php使用递归与非递归实现折半查询的算法操作步骤与使用方法,需要的朋友可以参考下
系统包含的功能如下: (1) 根据指定学生个数,逐个输入学生信息; (2) 逐个显示学生表中所有学生的相关信息;...(9) 根据学号进行折半查找,要求使用非递归算法实现,成功返回此学生的姓名和成绩。 黑框控制台程序
6.中序遍历的非递归算法 7.先序遍历的非递归算法 8.后序遍历的非递归算法 9.层次的非递归算法 10.求二叉树的深度(后序遍历) 11.求树的深度 12.编写DFS算法的非递归函数。 13.用普里姆(Prim)算法构造最小生成树 14....
二分法查找,也称折半查找,是一种在有序数组中查找特定元素的搜索算法。查找过程可以分为以下步骤: ... // 非递归算法 function binary_search(arr, key) { var low = 0, high = arr.length - 1; while(low
实现一个学生管理系统,即定义一个包含学生信息(学号,姓名,成绩)的的顺序表,可以不考虑重名的情况,系统至少包含以下功能: ...(9) 根据学号进行折半查找,要求使用非递归算法实现,成功返回此学生的姓名和成绩。