1、顺序查找



对于一个无序的，即关键字没有排序的线性表来说，用所给的关键字与线性表中的所有记录逐个进行比较，直到成功或者失败。


平均查找长度：ASL=(n+1)/2


I、最不频繁使用法（LFU）：也叫作计数法，为线性表中的每条记录保存一个访问计数，并按照访问频率从高到低进行排序，而且一直按照这个顺序维护记录。这样，每当访问一条记录时，如果该记录的访问数已经大于它前面记录的访问数，这条记录就会在线性表中向前移动。很明显，这种方法为了保护访问计数需要占用空间，另外，该方法对记录访问频率随时间而改变的反应也不好。在频率计数中，一旦一条记录被访问了很多次，不管将来的访问次数怎样。它都一直位于线性表的前面。


II、最近最少使用法（LUR）：也叫作移至前端法，如果找到一条记录就把他移至线性表的最前面，而把其他记录后退一个位置。显然，这种方式使用链表来存储比较好实现。同时，该方法对访问频率的局部变化反应很好，这是因为如果一条记录在一段时间内被频繁访问，在短时间它就会靠近线性表的前边。现在，搜狗拼音、紫光等输入法，使用的都是这种方法，把当前常用的字和词都移至前端，有效的提高了输入汉字的速度。


III、转置（transpose）方法：也叫作调换方法，把找到的记录与它表中的前一条记录交换位置。这种方法无论是基于链表存储还是数组存储，都是很好的方法。随着时间的推移，最常使用的记录将移动到线性表的前面。曾经被频繁访问但以后不会再使用的记录将会慢慢的落到后面。该方法在大部分情况下对访问频率的变化有很好的反应。但是，也会出现一些极端的情况。例如，首先访问线性表的最后一条记录I，然后就把这条记录与倒数第二条记录J交换位置，使得J称为最后一条记录。如果接下来访问的依然是最后一条记录J，那么就会和倒数第二条记录I交换位置。如果访问序列恰好就这样在I和J之间不断交替，将总是查找该表的最后位置，而这两条记录始终不能往前移动。不过，这种情况在实际情况中很少出现。




2、折半查找（二分查找）



对于任何一个线性表，若其中的所有数据元素都按照关键字的大小呈递减或递增排列，则称为有序表。
折半查找首先要求查找表满足：查找表采用顺序存储（数组）结构，并且按关键字大小有序排列。


基本查找过程：每次将待查范围中间位置上的数据元素的关键字与给定值K比较，如果相等就查找成功；否则利用该位置将整个表划分成前、后两个子表，如果中间位置记录的关键字大于待查关键字，则继续在前半部分子表进行查找，否则就在后半部分子表进行查找，重复此过程，直到“查找成功”或“查找不成功”。


折半查找是典型的分治类算法，所以算法也可以利用递归来实现。


平均查找长度：ASL=((n+1)/n)*log2(n+1)-1，当n>50时，ASL约等于log2(n+1)-1


折半查找的有点2在于关键字的比较次数比较少，查找速度快，平均性能较好，但缺点是要求待查表必须为有序表，而且要基于顺序结构存储，这对于插入和删除操作来说是比较困难的。因此，折半查找适合于一经建立就很少改动，而且有需要经常查找的有序查找表。




3、索引查找（分块查找）



如果线性表既希望有较快的查找速度，有需要动态变化，则可以采用索引查找。索引查找又称为分块查找，它是一种性能介于顺序查找和折半查找之间的查找办法。


基本思想：1、把线性表分成若干块，每块包含若干记录，在每一块中记录的存放是任意的，但块与块之间必须是有序的（分块有序）。2、建立一个索引表，把每块中的最大关键字值以及每块的第一个记录在表中的位置和最后一个记录在表中的位置存放在索引项中。所以，索引表是一个有序表。


查找时，首先用待查找的关键字在索引表中查找，确定具有该关键字的结点应该在哪一个分块中，在索引中查找的方法可以采用顺序查找或是折半查找，然后再到相应的分块中顺序查找，即可得到查找结果。


第一个阶段以折半查找ASL约为log2(n/i+1)+(i+1)/2；若第一阶段以顺序查找ASL=(n+i^2)/(2*i)+1


索引查找的优点在于在线性表中插入一个或删除一个结点时，只要找到该结点应属于的块，然后在块内进行插入或删除运算。由于块内结点的存放是任意的，因此插入或删除比较容易，不需要移动大量的结点。插入可直接在块尾进行；如果待删的记录不是块中最后一个记录时，可将本块内最后一个记录移入被删记录的位置。因此，在某些情况下索引查找是比较容易实现的。

二分查找和顺序查找
1.顺序查找：对于长度为N的线性表，平均要进行N/2次比较，在最坏清空下进行N次比较

顺序查找适用于无序表或者链表线性表（不管无序还是有序）

2.二分查找：使用于顺序存储的有序表，对于长度为N的线性表，在最坏情况下进行log2n次比较。

概念：根据给定的值，在某个集合中确定该值所处的位置

查找算法（比较式查找算法分为）：

（1）基于线性表的查找。例如：顺序查找、折半查找、分块查找

（2）基于树的查找。例如二叉排序树、B树、AVL树

平均查找长度：为确定某元素在查找表中的位置需要和给定值进行比较的关键字个数的期望值，称为该查找算法查找成功的平均查找长度。

对于长度为n的查找表，查找成功的平均查找长度如下所示： 
ASL=∑i=1nPiCi


其中Pi为查找表中第i个记录的概率，且∑ni=1Pi=1，Ci为找到该记录时，曾经和给定值比较的关键字的个数

基于线性表的查找

顺序表的平均查找长度是ASLsucc=1/n(n−i+1)=(n+1)/2

折半查找：首先这种方法适用于有序的情况下，首先比较的是关键字key与给定值K的关系，可根据三种比较结果分出三种情况：

（1）如果k=key，则查找成功

（2）如果k<key，说明待查有元素在关键字key的记录之前

（3）如果k>key，说明待查元素在关键字key的记录之后



#include<stdio.h>

int search(int *ary, int k, int len);

int search(int *ary, int k, int len) {
    int low = 0;
    int high = len - 1;
    int mid = 0;

    while(low <= high) {
        mid = (low + high) / 2;
        printf("mid :  %d\n", mid);
        if(ary[mid] == k) {
            return mid;
        }else if(ary[mid] < k) {
            low = mid + 1;
        }else {
            high = mid - 1;
        }           
    } 

    return 0;   
}


void main(void) {
    int ary[10] = {12, 19, 25, 33, 46, 58, 64, 80};
    int res = search(ary, 46, 8);
    printf("%d ", res);
} 

基于树的查找



1. 二叉排序树（二叉查找树）

特征如下：

若它的左子树不空，则左子树上所有结点的值均小于根结点的值
若它的右子树不空，则右子树上所有结点的值均大于根节点的值
它的左、右子树也都分别是二叉排序树
查找过程如下：这个查找过程是与折半查找类似的，即逐步缩小查找的范围

若给定值等于根节点的关键字，则查找成功
若给定值小于根节点的关键字，则继续在左子树上进行查找
若给定值大于根节点的关键字，则就继续在右子树上进行查找
2. 平衡二叉树

满足以下性质的二叉排序树：

二叉排序树中任何一个结点的左子树和右子树高度相差的绝对值最多为1
它的左右子树都是平衡二叉树
3.B树和B+树

B树在文件系统和数据库系统中使用比较多，适用于组织动态的索引结构

一个m阶B树的定义如下：

树中每个结点至多有m个子结点
除根结点和叶子结点之外，其他每个结点至少有[m/2]个子节点
若根节点不是叶子结点，则根节点至少有两棵子树
所有的叶子结点在同一层，可以有[m/2]−1到m−1个关键字，并且叶子结点所在的层数为树的深度
有k个子节点的分支结点恰好包括k−1个关键字
散列

零比较次数：这类查找算法属于第二类查找方法，散列法，也被称为哈希法、杂凑法或关键字地址计算法。这是一种非常高效的查找方法。

采用散列方式进行查找时必须解决的两个问题是：

如何构造恰当的hash函数，使得结点“分布均匀”，尽量少的冲突
一旦发生冲突，如何处理冲突
几种常用的hash函数构造方法：

除留余数法
数字分析法
立方/平方取中法
分段叠加法
基数转换法
处理冲突的方法：

（1）开放定址法

线性探测再散列

冲突发生时，顺序查看表中下一个单元，直到查找到一个空单元或找遍全表，利用取余%运算，因而整个表可以成为一个首尾连接的循环表，在查找时，类似于循环队列，表尾的后面是表头，表头的前边是表尾
二次探测再散列
随机探测再散列
（2）链地址法

链地址法解决冲突的基本思想是：把所有具有地址冲突的关键字在同一个单链表中，若哈希表的长度为m，则可将哈希表定义为一个有m个头指针组成的指针数组，散列地址为i的记录，均插入到以指针数组第i个单元为头指针的单链表中。

基于线性表的查找：具体分为顺序查找法、折半查找法以及分块查找法。三种方式都非常简单，在此引出一个概念，平均查找长度。即为了确定数据元素在列表中的位置，需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度。对于长度为n的列表，查找成功时的平均查找长度为ASL = P1C1 + P2C2 + P3C3 + … + PnCn = ∑PiCi (i=i..n)  其中Pi为查找列表中第i个元素的概率，Ci为找到列表中第i个元素时，已经进行过的关键字比较次数。那么顺序表的平均查找长度就是1/2(n+1)，折半查找的平均查找长度为((n+1)/n)log(n+1)-1，当索引使用顺序查找时的分块查找的平均查找长度为1/2(n/s+s)+1，当索引使用二分查找是的平均查找长度为log(n/s+1)+s/2。其中表的长度为n，分为b块，每块含有s个元素。

// 二分查找，返回下标
template<typename T>
int BinSearch(T *array, int len, T key)
{
    int lowIndex = 0, highIndex = len - 1;
    int midIndex = 0;
    while (lowIndex <= highIndex)
    {
        midIndex = (lowIndex + highIndex) / 2;
        if (key == array[midIndex])
            return midIndex;
        else if (key < array[midIndex])
            highIndex = midIndex - 1;
        else
            lowIndex = midIndex + 1;
    }
    return -1;
}

基于树的查找：又称树表查找法，主要包括二叉排序树、平衡二叉排序树和B_树。这里主要介绍二叉排序树。 
二叉排序树的插入： 

        1、若二叉排序树是空树，则key(待插入值)成为二叉排序树的根； 

        2、若二叉排序树非空，则将key与二叉排序树的根比较，如果key等于根节点的值，停止插入； 

           如果key小于根节点的值，则将key插入左子树； 

           如果key大于根节点的值，则将key插右左子树。



// 向二叉排序树中插入
void InsertBT(BitTree **root, DataType key)
{
    if ((*root) == NULL)
    {
        *root = new BitTree();
        (*root)->m_data = key;
        (*root)->m_lchild = (*root)->m_rchild = NULL;
    }
    else
    {
        if (key < (*root)->m_data)
        {
            InsertBT(&(*root)->m_lchild, key);
        }
        else if (key >(*root)->m_data)
        {
            InsertBT(&(*root)->m_rchild, key);
        }
    }
}


二叉排序树的删除： 

        1、若p(待删除的节点)为叶子节点，则可将其直接删除。 

        2、若p只有左子树，或者只有右子树，则可将p的左子树或右子树直接改为p的双亲节点的左子树。 

        3、若p既有左子树，又有右子树，则首先找到p的左子树中最大的值，并将其值赋给p节点，然后删掉这个最大值。偷梁换柱。



// 在二叉排序树中删除
void DeleteBT(BitTree **root, DataType key)
{
    BitTree *pCul = *root, *pParent = NULL;
    while (pCul != NULL)
    {
        if (key == pCul->m_data)
        {
            break;
        }
        pParent = pCul;
        if (key < pCul->m_data)
        {
            pCul = pCul->m_lchild;
        }
        else
        {
            pCul = pCul->m_rchild;
        }
    }
    if (pCul == NULL)
    {
        return;
    }
    if (pCul->m_lchild == NULL)
    {
        if (pParent == NULL)
        {
            *(root) = pCul->m_rchild;
            delete pCul;
            pCul = NULL;
        }
        else
        {
            if (pParent->m_lchild == pCul)
            {
                pParent->m_lchild = pCul->m_rchild;
            }
            else if (pParent->m_rchild == pCul)
            {
                pParent->m_rchild = pCul->m_rchild;
            }
        }
        delete pCul;
        pCul = NULL;
    }
    else
    {
        BitTree *pTempCul = pCul->m_lchild, *pTempParent = pCul;
        while (pTempCul->m_rchild != NULL)
        {
            pTempParent = pTempCul;
            pTempCul = pTempCul->m_rchild;
        }
        pCul->m_data = pTempCul->m_data;
        if (pCul == pTempParent)
        {
            pTempParent->m_lchild = pTempCul->m_lchild;
        }
        else
        {
            pTempParent->m_rchild = pTempCul->m_lchild;
        }
        delete pTempCul;
        pTempCul = NULL;
    }
    return;
}

二叉排序树的平均查找长度为log n；

计算式查找法：哈希法 

    处理冲突的方法：1、开放定址法，当key的hash地址出现冲突时，以此地址为基础，在产生一个hash地址，直到不冲突为止。 

            2、再hash法，同时构造多个不同的hash函数，当hash地址发生冲突时，再使用另一个hash函数重新计算，并写入新表。 

            3、链地址法，将所有出现冲突的元素构成一个单链表。 

            4、建立公共溢出区，将hash表分为基本表与溢出表两部分，没发生冲突的放在基本表，否则放在溢出表。

拓展：查找一组序列中最小的K个数 

    将这组序列中前k个数维护成一个最大堆，然后遍历序列，将序列中的元素与最大堆的首元素进行比较，如果序列中的元素大于堆中的元素，那么他就一定大于堆中其他元素，即不是最小的k个数，丢弃。否则，交换。在STL中，set和multiset都是使用红黑树实现的，所以这两个容器可以用来模拟最大堆。multiset允许插入元素重复。



void SearchLeastNum(const vector<DataType> &array, const size_t k, multiset<DataType, greater<DataType>> &least)
{
    least.clear();
    if (k < 1 || array.size() < k)
    {
        return;
    }
    auto vIt = array.begin();
    for (; vIt != array.end(); ++vIt)
    {
        // 先初始化一个包含K个元素的最大堆
        if (least.size() < k)
        {
            least.insert(*vIt);
        }
        // 如果要插入的元素小于最大堆的最大值，替换
        else
        {
            auto sIt = least.begin();
            if (*vIt < *sIt)
            {
                least.erase(sIt);
                least.insert(*vIt);
            }
        }
    }
}