C/C++查找大总结（未完）

二分查找

定义

对已经排好序的数组进行查找
对数组进行操作
在查找失败最多次数$ K=\lfloor log2^{n}\rfloor +1 $(向下取整加一)

二分查找的时间复杂度:$ \displaystyle\frac{n}{2^k} = 1,K = log2^n $

---

由于简书不可以读取latex公式，这里推荐到我的主页去看。请点击!

---

二分查找的代码

int BinaryChop(int Num[],int nCount,int nValue)
{
    int max_index = nCount-1;
    int min_index = 0;
    int Mid = 0;
    while (min_index<=max_index)
    {
        Mid = (max_index+min_index)/2;
        if(Num[Mid] == nValue)
            return Mid;
        if(Num[Mid]>nValue)
        {
            max_index = Mid-1;
        }else
        {
            min_index = Mid+1;
        }
    }
    return -1;
}

HashChop（哈希查找）

定义：对已经建好散列表的数据进行查找。

哈希是查找速度最快的算法。
缺点:空间消耗非常大。

步骤

1. 分析数据并定散列函数。
2. 决定哈希冲突的解决办法。
3. 根据散列函数建散列表。
4. 对已经建好的散列表进行查找。

对于以上步骤第一步到第三步是建立散列表的过程。

散列函数

我们一般用求整取余法。

1. 首先我们选取一个数M，这个数最好是质数（非硬性要求），但一定比数据元素个数小，因为在同时间复杂度下占用空间最小为宜，后面会提及。
2. 当M数确定下来后，我们定桶，桶为数据元素除以质数M的各个余数，也就是从0到M-1，元素除以质数M得桶所代表的余数，我们就把这个数据元素放入桶内，而且每个桶里只能放一个元素。
3. 而当数据元素除以质数M得余数相同时，由于桶内只能放一个元素，所以当出现余数相同的元素时而不能放入桶内时，就产生了哈希冲突。当我们解决完哈希冲突后，也就建完散列表，就可以查找了！

解决哈希冲突

1. 开放地址法

• 线性探测法：在冲突位置顺次后延一位放入桶内。也就是说同为余数4的话，后来的数据就放入余数5的桶里。
• 线性补偿法：首先定一个步长，遇到冲突时，按步长顺次后延步长的长度放入桶内。
• 随机探测法：找个随机数来当步长，解决冲突如上个办法。

2. 拉链法：

• 在每个桶内建立一个头添加的链表，每个桶内装的是相应链表的头指针，将后来的元素依次头添加在链表上。

举例图示

例如数组｛19，27，55，41，82，89，16，9，22，98，104，1，2，205，46｝

HashChop

代码

typedef struct node
{
    int nValue;
    int nIndex;
    struct node *pNext;
}MyHash;

#define M 7

MyHash **CreateHashTable(int arr[],int nLength)
{
    MyHash **pHash = NULL;
    MyHash *pTemp = NULL;
    int i;
    int nIndex;
    //申请哈希表表头
    pHash = (MyHash**)malloc(sizeof(MyHash*) * M);
    memset(pHash,NULL,sizeof(MyHash*) * M);

    //拉链法
    for(i = 0;i<nLength;i++)
    {
        nIndex = arr[i]%M;
        pTemp = (MyHash*)malloc(sizeof(MyHash));
        pTemp->nIndex = i;
        pTemp->nValue = arr[i];

        //头添加
        pTemp->pNext = pHash[nIndex];
        pHash[nIndex] = pTemp;
    }
    return pHash;
}

int HashChop(int arr[],int nLength,int nNum)
{
    MyHash **pHash = NULL;
    int nIndex;
    MyHash *pMark = NULL; 

    if(arr == NULL || nLength <=0) 
        abort();

    //建哈希表
    pHash = CreateHashTable(arr,nLength);

    //查询
    nIndex = nNum%M;
    pMark = pHash[nIndex];

    //遍历链表
    while(pMark)
    {
        if(pMark->nValue == nNum)
        {
            return pMark->nIndex;
        }
        else
        {
            pMark = pMark->pNext;
        }
    }

    return -1;
}