package com.my.test;
/**
* 折半查找(二分查找)的递归和非递归算法. 说明:
* 1、要求所查找的数组已有序,并且其中元素已实现Comparable<T>接口,如Integer、String等.
* 2、非递归查找使用search();,递归查找使用searchRecursively();
**/
public class BinarySearch<T extends Comparable<T>> {
private T[] data;// 要排序的数据
public BinarySearch(T[] data) {
this.data = data;
}
public int search(T key) {
int low;
int high;
int mid;
if (data == null) {
return -1;
}
low = 0;
high = data.length - 1;
while (low <= high) {
mid = (low + high) / 2;
//System.out.println("mid " + mid + " mid value:" + data[mid]);
if (key.compareTo(data[mid]) < 0) {
high = mid - 1;
} else if (key.compareTo(data[mid]) > 0) {
low = mid + 1;
} else if (key.compareTo(data[mid]) == 0) {
return mid;
}
}
return -1;
}
private int doSearchRecursively(int low, int high, T key) {
int mid;
int result;
if (low <= high) {
mid = (low + high) / 2;
result = key.compareTo(data[mid]);
//System.out.println("mid " + mid + " mid value:" + data[mid]);
if (result < 0) {
return doSearchRecursively(low, mid - 1, key);
} else if (result > 0) {
return doSearchRecursively(mid + 1, high, key);
} else if (result == 0) {
return mid;
}
}
return -1;
}
public int searchRecursively(T key) {
if (data == null) {
return -1;
}
return doSearchRecursively(0, data.length - 1, key);
}
public static void main(String[] args) {
Integer[] data = { 1, 4, 5, 8, 15, 33, 48, 77, 96 };
BinarySearch<Integer> binSearch = new BinarySearch<Integer>(data);
System.out.println("Key index:" + binSearch.search(33));
System.out.println("Key index:" + binSearch.searchRecursively(3));
String[] dataStr = { "A", "C", "F", "J", "L", "N", "T" };
BinarySearch<String> binSearch1 = new BinarySearch<String>(dataStr);
System.out.println("Key index:" + binSearch1.search("T"));
}
}
分享到:
相关推荐
用C语言开发的递归和非递归二分查找算法,具体内容详见代码
分别用递归和非递归方法实现二分查找算法 的完整程序,indexof()返回的是循环实现的二分法查找,getindex()实现的是递归算法实现的二分法查找。
这里本人自己写的是折半查找算法(又称二分查找)的c++代码的实现, 用的是递归的方法和非递归的方法, 里面的代码已经编译通过,并且优化好, 有需要的朋友可以下载借鉴一下
二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。首先,假设表中元素是按升序排列,将表...
二分法查找,也称折半查找,是一种在有序数组中查找特定元素的搜索算法。查找过程可以分为以下步骤: ... // 非递归算法 function binary_search(arr, key) { var low = 0, high = arr.length - 1; while(low
编写程序生成下面所示的二叉树,并采用中序遍历的非递归算法对此二叉树进行遍历 四、思考与提高 1.如何计算二叉链表存储的二叉树中度数为1的结点数? 2.已知有—棵以二叉链表存储的二叉树,root指向根结点,p...
5.3.2 折半查找操作示例 142 5.4 数据结构中的查找算法 145 5.4.1 顺序表结构中的查找算法 145 5.4.2 链表结构中的查找算法 148 5.4.3 树结构中的查找算法 151 5.4.4 图结构中的查找算法 152 5.5 小结 153 ...
Java编写的山寨QQ,多人聊天+用户在线,程序分服务端和客户端,典型C/S结构, 当用户发送第一次请求的时候,验证用户登录,创建一个该qq号和服务器端保持通讯连接得线程,启动该通讯线程,通讯完毕,关闭Scoket...
归并排序(非递归算法) 基数排序 实现图的存储结构 图的深度遍历 图的广度遍历 二叉排序树的复制 计算二叉树的结点个数 删除单链性表中值相同的多余结点 删除线性表中所有值为x的元素 Josephus问题 利用...
折半查找 给歌手打分 航线设置 数字全排列 借书方案 求直角三角形 二分排序 抢30 求回文数 斐波那契数列(递推法) 分块查找 求帕斯卡三角(杨辉三角) 箱子问题(贪婪法) 寻找文件(递归法) 求最大公约数(递归法) 取不...
7.13 递归函数的非递归求解 7.14 任意长度整数加法 第8章 数值计算问题 8.1 递推化梯形法求解定积分 8.2 求解低阶定积分 8.3 迭代法开平方运算 8.4 牛顿法解方程 8.5 欧拉方法求解微分方程 8.6 改进的欧拉方法求解...
14.折半查找 15.给歌手打分 16.航线设置 17.数字全排列 18.借书方案 19.求直角三角形 20.二分排序 21.抢30 22.求回文数 23.斐波那契数列(递推法) 24.分块查找 25.求帕斯卡三角(杨辉三角) 26.箱子问题(贪婪法) 27....
利用堆栈类,将本题a和b的代码改成非递归的方式。 实验报告要求: 按要求写出完整的实验代码; <br>实验四 综合(课程设计) 内容及步骤: 1、假定一维数组a[n]中的每个元素值均在[0,200]区间内,用C++...
07递归算法_折半查找.mp4 08.Permutations.mp4 09.插入排序.mp4 10.快速排序.mp4 11.归并排序.mp4 12.顺序栈.mp4 13.顺序队列.mp4 14.链表的基本概念.mp4 15.单链表的基本运算.mp4 16.循环单链表.mp4 17....
折半查找 C. 分块查找 D. 哈希表查找 -----------------选择: 15春《计算机科学导论》作业3 单选题 多选题 判断题 三、判断题(共 6 道试题,共 30 分。) 1. 批处理操作系统(Batch Processing Operating System...
1.4.10 中序非递归遍历二叉树(链式结构)(1) 174 范例1-64 中序非递归遍历二叉树 174 ∷相关函数:InOrderTraverse函数 1.4.11 中序非递归遍历二叉树(链式结构)(2) 177 范例1-65 中序非递归遍历二叉树 ...
1.4.10 中序非递归遍历二叉树(链式结构)(1) 174 范例1-64 中序非递归遍历二叉树 174 ∷相关函数:InOrderTraverse函数 1.4.11 中序非递归遍历二叉树(链式结构)(2) 177 范例1-65 中序非递归遍历二叉树 ...
1.4.10 中序非递归遍历二叉树(链式结构)(1) 174 范例1-64 中序非递归遍历二叉树 174 ∷相关函数:InOrderTraverse函数 1.4.11 中序非递归遍历二叉树(链式结构)(2) 177 范例1-65 中序非递归遍历二叉树 ...
15. 若有18个元素的有序表存放在一维数组A[19]中,第一个元素放A[1]中,现进行二分查找,则查找A[3]的比较序列的下标依次为( ) A. 1,2,3 B. 9,5,2,3 C. 9,5,3 D. 9,4,2,3 16. 对n个记录的文件进行快速...