折半查找(binary search) 算法示例

折半查找, 又称二分查找(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:\eclipse\dropins\stdlib.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);
        }
    }
}

输出:

返回栏目页：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索数组
， int
， 文件
， 数据
， noclassdeffounderror
， java 算法 数据...
， 输出
， 折半查找
， stdlib hqsortc语言
， kepler
， 成功
， 判断执行成功
， Arrays简单示例
折半插入排序
binary search 算法、折半查找算法、折半查找的递归算法、折半查找算法c语言、java折半查找算法，以便于您获取更多的相关知识。