查找算法——顺序查找

基于无序链表的顺序查找：在查找中我们一个一个地顺序遍历符号表中的所有键并使用equals()方法来寻找与被查找的键匹配的键。

无序链表查找的性能

上面get()方法中查找第一个键需要1次比较，查找第二个需要2次比较，如此这般，平均比较次数为(1+2+...+N)/N，也就是(N+1)/2~N/2。比较的总次数和查找次数与插入次数的乘积成正比，所以基于链表的实现以及顺序查找是非常低效的。

1、顺序查找基于无序链表

public class SequentialSearchST<Key, Value> {
    
    private Node first;
    Node next;
    private class Node{
        Key key;
        Value val;
        Node next;

        public Node(Key key, Value val, Node next) {
            this.key = key;
            this.val = val;
            this.next = next;
        }
    }

    public SequentialSearchST(Node first, Node next) {
        this.first = first;
        this.next = next;
    }

    public Value get(Key key) {
        for (Node x = first; x != null; x = x.next) {
            if (key.equals(x.key)) return x.val;
        }
        return null;
    }

    public void put(Key key, Value value) {
        for (Node x = first; x != null; x = x.next) {
            if (key.equals(x.key)) {
                x.val = value;
                return;
            }
            first = new Node(key, value, first);
        }
    }
}

2、二分查找基于有序数组

public class BinarySearchST<Key extends Comparable<Key>, Value> {

    private Key[] keys;
    private Value[] values;
    private int N;

    public BinarySearchST(int capacity) {
        keys = (Key[]) new Comparable[capacity];
        values = (Value[]) new Object[capacity];
    }

    public int size() {
        return N;
    }

    public Value get(Key key) {
        if (key == null) return null;
        int i = rank(key);
        if (i < N && keys[i].compareTo(key) == 0) {
            return values[i];
        } else {
            return null;
        }
    }

    public int rank(Key key) {
        int lo = 0, hi = N - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            int cmp = key.compareTo(keys[mid]);
            if (cmp < 0) hi = mid - 1;
            else if (cmp > 0) lo = mid + 1;
            else return mid;
        }
        return lo;
    }

    public void put(Key key, Value val) {
        int i = rank(key);
        if (i < N && keys[i].compareTo(key) == 0) {
            values[i] = val;
            return;
        }
        for (int j = N; j > i; j--) {
            keys[j] = keys[j - 1];
            values[j] = values[j - 1];
        }
        keys[i] = key;
        values[i] = val;
        N++;
    }
}