首页 / 软件开发 / 数据结构与算法 / 折半查找（binary search） 算法示例

折半查找（binary search） 算法示例2015-09-30折半查找, 又称二分查找（binary search）, 需要数组有序（sort）, 通过比较数组的中间数据（中心偏向较小的方法）, 确定查找值的范围;

直到中值等于查找值, 则查找成功; 如果未成功, 则重置数据, 判断首尾位置的大小, 再进行中值比较; 判断失败, 则数据不存在;

注意:

1. Eclipse无法重定向（redirect）输入文件（file）, 只能读入数据;

2. 使用cmd重定向输入文件, 则需要解压"stdlib.jar", 取出相应的class（In, Out, StdIn, StdOut）, 放入执行目录, 否则会报错:

错误: java.lang.NoClassDefFoundError, 即找不到相应的class文件, 会出现Eclipse可以执行, cmd不能执行的情况;

代码主要功能: 判断是否查找成功, 失败则输出查找数据;

命令行: java -classpath D:eclipsedropinsstdlib.jar; BinarySearch tinyW.txt < tinyT.txt

代码如下:

/** 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）;}}}

输出: