首页 > 代码库 > 算法5-4:1d范围查找

算法5-4:1d范围查找

有一个整数集合,求所有介于x到y之间的所有整数


实现方法


非顺序数组:复杂度是N,比较慢

顺序数组:查找操作的复杂度是lgN,插入操作的复杂度是N

二叉查找树:复杂度是logN,比较快


代码


下面这段代码用于统计lo到hi之间的整数个数

public int count(Key lo, Key hi) {
    if(contains(hi)) return rank(hi) - rank(lo) + 1;
    else return rank(hi) - rank(lo);
}


下面展示了完整的代码:

public class Search1D<Item extends Comparable<Item>> {
    private BST<Item, Item> tree;
 
    public Search1D() {
        tree = new BST<Item, Item>();
    }
 
    public void add(Item item) {
        tree.insert(item, item);
    }
 
    // 求区间[a, b)范围内的元素数量
    public int count(Item a, Item b) {
        return tree.rank(b) - tree.rank(a);
    }
}