package com.snail.basic;


public class SequentialSearchST<Key, Value> {
    // 鏈表首結(jié)點(diǎn)
    private Node first;

    private class Node {
        // 鏈表結(jié)點(diǎn)定義
        Key key;
        Value val;
        Node next;

        public Node(Key key, Value val, Node next) {
            this.key = key;
            this.val = val;
            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 val) {
        // 查找給定的鍵，找到則更新其值，否則在表中新建結(jié)點(diǎn)
        for (Node x = first; x != null; x = x.next)
            if (key.equals(x.key)) {
                // 命中 更新
                x.val = val;
                return;
            }
        // 未命中新建結(jié)點(diǎn)
        first = new Node(key, val, first);
    }

}

package com.snail.basic;

/**
 * 二分查找基于有序數(shù)組
 * 
 * @param <Key> 有序排列的鍵
 * @param <Value> 鍵對(duì)應(yīng)的值
 */
public class BinarySearchST<Key extends Comparable<Key>,Value> {
    private Key[] keys;
    private Value[] vals;
    private int N;
    public BinarySearchST(int capacity){
        keys = (Key[]) new Comparable[capacity];
        vals = (Value[]) new Object[capacity];
    }
    public int size(){
        return N;
    }
    public Value get(Key key){
        int i = rank(key);
        if(i<N&&keys[i].compareTo(key)==0)return vals[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){
            vals[i] = val;return;
        }
        for (int j = N; j > i; j--) {
            keys[j]= keys[j-1];
            vals[j] = vals[j-1];
        }
        keys[i]=key;
        vals[i]=val;
        N++;
    }
}