算法3.2 二分查找符号表(基于有序数组)

算法3.2 有序数组中的二分查找

实现:这种符号表使用一对平行的数组,一个存储键,一个存储值,核心是rank()方法,返回表中小于给点键的键数,对于get(),只要键存在,rank()即可指明位置,put()同理

public class BinarySearchST<Key extends Comparable<Key>, Value>{
    private Key[] keys;
    private Value[] values;
    private int N;
    public BinarySearchST(int capacity){
        keys = (Key[])new Object[capacity];
        values = (Value[])new Object[capacity];
    }
    private boolean isEmpty(){ return N==0;}
    private int rank(Key key){
        int lo = 0, hi = N-1;
        while (lo <= hi){
            int mid = lo + (hi-lo)/2;
            int cmp = keys[mid].compareTo(key);
            if (cmp < 0) lo = mid+1;
            else if (cmp > 0) hi = mid-1;
            else return mid;
        }
        return lo;//return保证即便没有该键也能返回小于该键的键数
    }
    //递归实现
    private int rank(Key key, int lo, int hi){
        if(lo > hi) return lo;
        int mid = lo + (hi-lo)/2;
        int cmp = keys[mid].compareTo(key);
        if (cmp < 0) return rank(key, mid+1, hi);
        else if (cmp > 0) return rank(key, lo, mid-1);
        else return mid;
    }
    private int size(){ return N;}
    private Value get(Key key){
        if (isEmpty()) return null;
        int i = rank(key);
        if (i < N && keys[i].compareTo(key) == 0) return values[i];
        else return null;
    }
    private void put(Key key, Value value){
        int i = rank(key);
        if (i < N && keys[i].compareTo(key) == 0){
            values[i] = value;
            return;
        }
        for (int j = N-1; j >= i; j--){
            keys[j] = keys[j+1];
            values[j] = values[j+1];
        }
        keys[i] = key;
        values[i] = value;
        N++;
    }
    private void delete(Key key){
        if(isEmpty()) return;
        int i = rank(key);
        if (!(i < N && keys[i].compareTo(key) == 0)) return;
        for (int j = N-1; j > i; j--){
            keys[j-1] = keys[j];
            values[j-1] = values[j];
        }
    }
}

说明

• 对于算法中递归的rank(key, 0, N-1),当表中存在该键,返回该键的位置,即排名,但即便表中不存在该键,rank()还是返回表中小于它的键的数量,当rank为迭代实现时,该性质还是满足.

算法分析

• 在N个键的有序数组中二分查找最多需要(lgN+1)次比较,无论是否成功
• 向大小N的有序数组中插入一个新元素在最坏情况下访问N²次数组