算法复习 (二) 查找-顺序查找和二分查找

发表于 2018-09-25 更新于 2021-07-07 分类于技术文档

本文字数： 7.1k 阅读时长 ≈ 6 分钟

算法复习 (二) 查找-顺序查找和二分查找，主要内容包括：符号表（符号表的删除操作、键的比较），无序链表的顺序查找（结点结构、增删查等操作实现），基于有序数组的二分查找（实现代码、结构、增删查等操作、分析、BinarySearchST的操作的成本），两者的比较，符号表的各种实现的优缺点等

算法复习 (二) 查找-顺序查找和二分查找

第一节符号表

定义：存储要查找的信息的某种数据结构，有时也被叫做字典（如英文字典中键即单词，值即对应的定义、发音和词源等），支持两种操作（插入和查找）。

通过三种经典的数据类型可以实现高效的符号表：

二叉查找树
红黑树
散列表

特点：键唯一，显式非空，值隐式非空（方便延时删除），可重复，可以看作是Java中的映射（Map）。

1.1 符号表的删除操作

延时删除：将键对应的值置空，在某个时刻删除所有空值键，put(key, null) 。
及时删除：立刻删除指定的键，delete(key) 。

为了保证任意时刻值都不为空，一般只采用及时删除。

void put(Key key, Value val){
       // 保证表中任何键的值都不为空
       if(val == null) {
           delete(key);
           return;
       }
       ......
   }

1.2 键的比较

判断键是否存在于表内，比较键的大小等都需要对键进行判断。相等根据对象等价性来判断，Java即 equals() ，相关内容参考：equals和hashCode异同。

符号表的键往往都是Comparable的对象，通过此特性可以实现符号表的有序性。

1.3 常见应用

应用	查找的目的	键	值
字典	找出单词的释义	单词	释义
图书索引	找出相关的页码	术语	一串页码
文件共享	找到歌曲的下载地址	歌曲名	计算机ID
账户管理	处理交易	账户号码	交易详情
网络搜索	找出相关网页	关键字	网页名称
编译器	找出符号的类型和值	变量名	类型和值

1.4 API

1.4.1 符号表

public class ST<Key, Value> implements Iterable<Key> {
    // 创建一张符号表
    ST();
    
    // 将键值对存入表中（若值为空则将键key从表中删除）
    void put(Key key, Value val);
    
    //获取键key对应的值（若键key不存在则返回null）
    Value get(Key key);
    
    // 从表中删除键key（及其对应的值）
    void delete(Key key);
    // 默认实现：put(key, null);
    
    // 键key在表中是否有对应的值
    boolean contains(Key key);
    // 默认实现：return get(key) != null;
    
    // 表是否为空
    boolean isEmpty();
    // 默认实现：return size() == 0;
    
    // 表中键值对的数量
    int size();
    
    // 表中所有键的集合
    Iterable<Key> keys();
}

1.4.2 有序符号表

常见的应用场景中，键应该是 Comparable 的对象，相应的即有序符号表，其API如下所示：

public class ST<Key extends Comparable<Key>, Value> implements Iterable<Key> {
    // 创建一张符号表
    ST();
    
    // 将键值对存入表中（若值为空则将键key从表中删除）
    void put(Key key, Value val);
    
    //获取键key对应的值（若键key不存在则返回null）
    Value get(Key key);
    
    // 从表中删除键key（及其对应的值）
    void delete(Key key);
    // 默认实现：put(key, null);
    
    // 键key在表中是否有对应的值
    boolean contains(Key key);
    // 默认实现：return get(key) != null;
    
    // 表是否为空
    boolean isEmpty();
    // 默认实现：return size() == 0;
    
    // 最小的键
    Key min();
    
    // 最大的键
    Key max();
    
    // 小于等于key的最大键
    Key floor(Key key);
    
    // 大于等于key的最小键
    Key celling(Key key);
    
    // 小于key的键的数量
    int rank(Key key);
    
    // 排名为k的键
    Key select(int k);
    
    // 删除最小的键
    void deleteMin();
    // 默认实现：delete(min());
    
    // 删除最大的键
    void deleteMax();
    // 默认实现：delete(max());
    
    // [lo...hi]之间键的数量
    int size(Key lo, Key hi);
    // 默认实现：if(hi.compareTo(lo < 0))
    //             return 0;
    //          else if(contains(hi))
    //             return rank(hi) - rank(lo) + 1;
    //          else
    //             return rank(hi) - rank(lo)
    
    // 表中键值对的数量
    int size();
    
    // [lo...hi]之间的所有键，已排序
    Iterable<Key> keys(Key lo, Key hi);
    
    // 表中所有键的集合，已排序
    Iterable<Key> keys();
    // 默认实现：return keys(min(), max());
}

1.5 API

符号表可以通过统计比较次数，若内循环不进行比较的情况则统计数组访问次数。

第二节无序链表的顺序查找

链表是实现符号表的一个简单选择，每个结点都存储一个键值对，顺序查找即在查找中一个一个的顺序遍历符号表的所有键并使用 equals() 方法来寻找与被查找的键相匹配的键。

实现代码： 顺序查找-SequentialSearchST

2.1 结点结构

//链表首结点
private Node first;
//定义链表结点
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;
    }
}

2.2 增删查等操作实现

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){
    //查找给定的键，找到则更新，否则在表中新建结点，保证Key唯一
    for(Node x = first;x != null;x = x.next) {
        if (key.equals(x.key)) {//命中，更新
            x.val = val;
            return;
        }
    }
    first = new Node(key,val,first);//未命中，新建结点
}

public int size(){//返回链表大小
    int count = 0;
    for(Node x = first;x != null;x = x.next)
        count++;
    return count;
}

public Node delete(Key key){//删除链表结点
    Node lastNode = null;//上个结点
    Node node = null;//删除结点
    for(Node x = first;x != null;x = x.next){
        if(key.equals(x.key)){//命中
            node = x;
            if(lastNode != null){//若上个结点不为空，连接上个结点和后个结点
                lastNode.next = node.next;
            }else {//若上个结点为空，后个结点为首节点
                first = x.next;
            }
            return node;
        }
        lastNode = x;
    }
    return null;//未找到Key
}

@SuppressWarnings("unchecked")
public Key[] keys(){//返回链表的键数组
    Key[] keys = (Key[])new Comparable[size()];
    int count = 0;
    for(Node x = first;x != null;x = x.next)
        keys[count] = x.key;
    return keys;
}

分析： 对于有N对键值的基于无序链表的符号表，未命中的查找和插入操作都需要N次比较。向一个空表中插入N个不同的键需要N^2/2次比较。

第三节基于有序数组的二分查找

3.1 实现代码

二分查找-BinarySearchST

3.2 结构

private Key[] keys;
private Value[] vals;
private int N;
public BinarySearchST(int capacity){//构造器中初始化数组
    keys = (Key[]) new Comparable[capacity];
    vals = (Value[]) new Object[capacity];
}

3.3 增删查等操作

public int size(){
    return N;
}

public Value get(Key key){//有Key则返回val，无则返回null，判断key是否相等，是根据其compareTo方法
    if(isEmpty()) return null;
    //二分查找获取key下标，未查到返回0或N，查到
    int i = rank(key);
    if(i < N && keys[i].compareTo(key) == 0)
        return vals[i];
    else
        return null;
}

public boolean isEmpty(){
    return N == 0;
}

public int rank(Key key){//二分查找，未查询到返回0或N，查到则返回下标
    //使用有序数组是为了根据索引减少每次查找所需要的比较次数
    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;i--){
        keys[j] = keys[j-1];
        vals[j] = vals[j-1];
    }
    keys[i] = key;
    vals[i]= val;
    N++;
}

public Value delete(Key key){//删除Key以及对应val
    if(isEmpty()) return null;
    int i = rank(key);
    if(i < N && keys[i].compareTo(key) == 0){//命中
        //分别从键数组和值数组中删除
        Value value = vals[i];
        //覆盖前个元素
        for(int n = i;n < N-1;n++){
            keys[n] = keys[n+1];
            vals[n] = vals[n+1];
        }
        //复制数组
        Key[] newKeys =(Key[]) new Comparable[N-1];
        Value[] newVals = (Value[]) new Object[N-1];
        for(int m = 0;m < N-1;m++){
            newKeys[m] = keys[m];
            newVals[m] = vals[m];
        }
        keys = newKeys;
        vals = newVals;
        return value;
    }
    else
        return null;
}

public Key min(){
    return keys[0];
}

public Key max(){
    return keys[N-1];
}

public Key select(int index){
    return keys[index];
}

//大于等于key的最小键
public Key ceiling(Key key){
    int i = rank(key);
    return keys[i];
}

//小于等于key的最大键
public Key floor(Key key){
    int i = rank(key);
    return keys[i];
}

public Iterable<Key> keys(Key lo,Key hi){
    MyQueue<Key> q = new MyQueue<Key>();
    for(int i = rank(lo);i < rank(hi);i++)
        q.enqueue(keys[i]);
    if(contains(hi))
        q.enqueue(keys[rank(hi)]);
    return q;
}

public boolean contains(Key key){
    if(isEmpty()) return false;
    //二分查找获取key下标，未查到返回0或N，查到
    int i = rank(key);
    if(i < N && keys[i].compareTo(key) == 0)
        return true;
    else
        return false;
}

3.4 分析

对于有N个键的有序数组，最多需要lgN+1次比较。二分查找减少了比较的次数，但无法减少运行所需的时间。因为在键是随机排列的情况下，构造一个基于有序数组的符号表所需要访问数组的次数是数组长度的平方级别。向大小为N的有序数组插入一个新的元素在最坏的情况下需要访问2N次数组，因此向一个空表中插入N个不同的键需要访问N^2次数组。

3.5 BinarySearchST的操作的成本

方法	运行所需时间的增长数量级
put()	N
get()	logN
delete()	N
contains()	logN
size()	1
min()	1
max()	1
floor()	logN
ceiling()	logN
rank()	logN
select()	1
deleteMin()	N
deleteMax()	1

二分查找的put和delete等方法有些过慢，不过相较SequentialSearchST顺序查找，BinarySearchST二分查找的比较次数(包含访问数组的次数)要少很多

第四节两者的比较

算法(数据结构)	最坏情况的成本 (N次插入后)		平均情况的成本 (N次随机插入后)		是否高效的支持有序性的相关操作
算法(数据结构)	查找	插入	查找	插入	是否高效的支持有序性的相关操作
顺序查找(无序链表)	N	N	N/2	N	否
二分查找(有序数组)	lgN	2N	lgN	N	是

目标： 同时保证查找和插入操作都是对数级别的算法和数据结构

第五节符号表的各种实现的优缺点

使用的数据结构	实现	优点	缺点
链表-顺序查找	SequentialSearchST	适用于小型问题	对于大型符号表很慢
有序数组-二分查找	BinarySearchST	最优的查找效率和空间需求能够进行有序性相关的操作	插入操作很慢
二叉查找树	BST	实现简单能够进行有序性相关的操作	没有性能上界的保证链接需要额外的空间
平衡二叉查找树	RedBlackBST	最优的查找和插入效率能够进行有序性相关的操作	链接需要额外的空间
散列表	SeparateChainHashST LinearProbingHashST	能够快速的查找和插入常见类型的数据	需要计算每种类型的数据的散列无法进行有序性相关的操作链接和空结点需要额外的空间

参考博客和文章书籍等：

《算法第4版》

因博客主等未标明不可引用，若部分内容涉及侵权请及时告知，我会尽快修改和删除相关内容

算法复习 (二) 查找-顺序查找和二分查找

第一节 符号表

1.1 符号表的删除操作

1.2 键的比较

1.3 常见应用

1.4 API

1.4.1 符号表

1.4.2 有序符号表

1.5 API

第二节 无序链表的顺序查找

2.1 结点结构

2.2 增删查等操作实现

第三节 基于有序数组的二分查找

3.1 实现代码

3.2 结构

3.3 增删查等操作

3.4 分析

3.5 BinarySearchST的操作的成本

第四节 两者的比较

第五节 符号表的各种实现的优缺点

第一节符号表

第二节无序链表的顺序查找

第三节基于有序数组的二分查找

第四节两者的比较

第五节符号表的各种实现的优缺点