折半查找(binary search) 详解及代码
本文地址:http://blog.csdn.net/caroline_wendy/article/details/17068019
折半查找, 又称二分查找(binary search), 需要数组有序(sort), 通过比较数组的中间数据(中心偏向较小的方法),
确定查找值的范围;
直到中值等于查找值, 则查找成功; 如果未成功, 则重置数据, 判断首尾位置的大小, 再进行中值比较; 判断失败,
则数据不存在;
注意:
1. Eclipse无法重定向(redirect)输入文件(file), 只能读入数据;
2. 使用cmd重定向输入文件, 则需要解压"stdlib.jar", 取出相应的class(In, Out, StdIn, StdOut),
放入执行目录, 否则会报错:
错误:java.lang.NoClassDefFoundError, 即找不到相应的class文件, 会出现Eclipse可以执行, cmd不能执行的情况;
代码主要功能: 判断是否查找成功, 失败则输出查找数据;
代码如下:
/*
* Algorithms.java
*
* Created on: 2013.12.02
* Author: Wendy
*/
/*eclipse std kepler, stdlib.jar*/
import java.util.Arrays;
public class Algorithms
{
/*折半查找算法(binary search)*/
public static int rank(int key, int[] a)
{
int lo = 0;
int hi = a.length - 1;
while (lo <= hi)
{
int mid = lo + (hi - lo) /2; //整数向下取整
if (key < a[mid]) hi = mid - 1;
else if(key > a[mid]) lo = mid + 1;
else return mid;
}
return -1;
}
public static void main(String[] args)
{
In in = new In(args[0]);
int[] whitelist = in.readAllInts(); //读取原始数组
Arrays.sort(whitelist); //排序
while(!StdIn.isEmpty()) //判断重定向数据是否为空
{
int key = StdIn.readInt();
if(rank(key, whitelist) == -1) //输出不存在的数据
StdOut.println(key);
}
}
}
输出:
分享到:
相关推荐
Beginning Algorithms----学习算法的好书,介绍各种算法!!!
Machine_Learning_Algorithms-master,Machine_Learning_Algorithms-master 配套数据集及源代码 Machine_Learning_Algorithms-master,Machine_Learning_Algorithms-master 配套数据集及源代码
MIT算法导论-Introduction to Algorithms-算法实现
data-algorithms-book, 数据算法书的MapReduce Spark Java和 Scala 数据算法。作者:Mahmoud Parsian ( mahmoud.parsian@yahoo.com )标题:数据算法:使用Hadoop和 Spark 扩展的食谱。这个GitHub存储库将托管所有的...
Algorithm-Problem-Solving-with-Algorithms-and-Data-Structures-using-Python.zip,使用python的算法和数据结构解决问题的代码,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
problem-solving-with-algorithms-and-data-structure-using-python 中文版
据说比《算法导论》更好的算法书籍......
Neo4j,用户手册,涵盖所有集成的图算法及应用场景,非常适合图算法的学习和应用
go-algorithms - 使用golang实现不同的算法和数据结构
Python-for-Algorithms--Data-Structures--and-Interviews, 关于算法和数据结构的Udemy课程文件 用于算法。数据结构和访谈的 python ! 欢迎访问Udemy课程的知识库: 用于算法,数据结构和访谈的python !这是为你...
###3:RandomContraction 使用 RandomContraction 算法查找图的最小割。 ###4:KosarajuSCC 使用 Kosaraju 算法在图中找到强连通分量。 ###5:Dijkstra 使用堆应用 Dijkstra 算法来找到从一个顶点到一个图的所有...
遗传算法Python程序 Hands-On-Genetic-Algorithms-with-Python-master.zip
[麻省理工学院-算法导论].Introduction.to.Algorithms--PPT
Machine-Learning-Algorithms-from-Scratch, 从零开始实现机器学习算法 Machine-Learning-Algorithms-from-Scratch从零开始实现机器学习算法。目前实现的算法:简单线性回归。数据集:来自Quandl的股票数据逻辑回归...
Introduction.to.Algorithms.-.Introduction.to.Algorithms.-.Introduction.to.Algorithms.-.Introduction.to.Algorithms.-.Introduction.to.Algorithms.-.Introduction.to.Algorithms.-.Introduction.to.Algorithms...
算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有...
算法导论第三版英文版 introduction-to-algorithms-3rd-edition
Algorithms - Robert Sedgewick, Kevin Wayne Algorithms - Robert Sedgewick, Kevin Wayne 视频 算法 普林斯顿
Algorithm-Cormen-Algorithms-Data-Structures.zip,《算法导论,第三版-CLRS》一书中算法的实现和数据结构,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
本资源中包括聚类分析算法实现,基于时间序列分析的聚类算法实现,主要应用于股票时间序列等的数据分析,clustering-algorithms-master