《算法4第一章》笔记（一）二分查找(1)

问题说明：

从一组有序整形数组中找出指定的数。

源码：

package edu.princeton.cs.algs4;

import java.util.Arrays;

public class BinarySearch {

    private BinarySearch() {
    }

    public static int indexOf(int[] a, int key) {
        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]) {
                    return mid;
                }

                lo = mid + 1;
            }
        }

        return -1;
    }

    /** @deprecated */
    @Deprecated
    public static int rank(int key, int[] a) {
        return indexOf(a, key);
    }

    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 (indexOf(whitelist, key) == -1) {
                StdOut.println(key);
            }
        }

    }
}

程序输入取自tinyT.text文件，内容为

23
50
10
99
18
23
98
84
11
10
48
77
13
54
98
77
77
68

程序入口

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();
        // 从console输入一个数字，使用indexOf方法判断是否存在,存在就打印出来
        if (indexOf(whitelist, key) == -1) {
            StdOut.println(key);
        }
    }

}

算法逻辑分析

public static int indexOf(int[] a, int key) {
    int lo = 0;// 区间最小值的索引
    int hi = a.length - 1;// 区间最大值的索引

    while(lo <= hi) {
        int mid = lo + (hi - lo) / 2;// 1.取出区间中间的索引
        // 2.如果中间的数大于key，则hi所有右边的数，全部大于key，舍弃
        if (key < a[mid]) {
            hi = mid - 1;
        } else {
            // 3.只有当相等时,即为找到了
            if (key <= a[mid]) {
                return mid;
            }
            // 4.反之，如果中间的数小于key,则lo所有左边的数，全部小于key，舍弃
            lo = mid + 1;
        }
    }
    // 全部循环发现找不到，返回-1
    return -1;
}