二分法查找

一 参考文档

https://zhangjia.io/959.html

https://zhidao.baidu.com/question/175408439483296444.html

二 代码参考

https://gitee.com/cakin24/Algorithm/tree/master/src/main/java

三 代码结构

四 核心代码

package BinarySearch;

import common.In;
import common.StdOut;
import java.util.Arrays;
import java.util.*;

public class BinarySearch {

    private BinarySearch() {
    }
    // 二分法查找的关键代码
    public static int indexOf( int[] a, int key ) {
        int lo = 0;
        int hi = a.length - 1;
        while (lo <= hi) {
            // Key is in a[lo..hi] or not present.
            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 ) {
        Scanner scan = new Scanner(System.in);
        // read the integers from a file
        In in = new In(args[0]);
        int[] whitelist = in.readAllInts();

        // 排序
        Arrays.sort(whitelist);

        // 读出要找的关键字，如果没有查找到，则输出
        while(scan.hasNextInt()) {
            int key = scan.nextInt();
            if (BinarySearch.indexOf(whitelist, key) == -1)
                StdOut.println(key);
        }
    }
}

五 测试

1 参数配置

2 运行

4      # 输入4
4      # 输出4，因为4在查找队列中是不存在的
1      # 输入1，无输出，因为它是存在的
608593 # 输出608593，无输出，因为它是存在的