查找的四种算法比较

顺序查找、二分查找、二叉搜索树、Hash表

1. 顺序查找

设想有一个1M的数据，我们如何在里面找到我们想要的那个数据。此时数据本身没有特征，所以我们需要的那个数据可能出现在数组的各个位置，可能在数据的开头位置，也可能在数据的结束位置。这种性质要求我们必须对数据进行遍历之后才能获取到对应的数据。

int find(int array[], int len, int val)
{
    if(array == NULL && length == 0)    return -1;
    for(int i=0;i<len;i++){
        if(val == array[i])
            return i;
    }
    return -1;
}

分析：由于我们不清楚这个数据判断究竟需要多少次。但是，我们知道，这样一个数据查找最少需要1次，那么最多需要n次，平均下来可以看成是（1+n）/2，差不多是n的一半。我们把这种比较次数和n成正比的算法复杂度记为o（n）。

2. 二分查找

如果数据排列地非常整齐，那结果会是什么样的呢？就像在生活中，如果平时不注意收拾整齐，那么找东西的时候非常麻烦，效率很低；但是一旦东西放的位置固定下来，所有东西都归类放好，那么结果就不一样了，我们就会形成思维定势，这样查找东西的效率就会非常高。那么，对一个有序的数组，我们应该怎么查找呢？二分法就是最好的方法。

int BinaryFind(int array[], int len, int val)
{
    if(array == NULL && length == 0)    return -1;
    int start = 0, end = len-1, middle=0;
    while(start<=end){
        middle = (start + end)/2;
        if(val == array[middle])    return middle;
        else if(val > array[middle])    start = middle+1;
        else end = middle-1;
    }
    return -1;
}

分析：上面我们说到普通的数据查找算法复杂度是o（n）。那么我们可以用上面一样的方法判断一下算法复杂度。这种方法最少是1次，那么最多需要多少次呢？我们发现最多需要log（n+1）/log（2）即可。

3. 二叉搜索树

二叉搜索树是二分查找的二叉树实现，二叉搜索树每个结点都有作为搜索依据的关键码，，所有结点的管家吗互不相同；左子树（若存在）上的所有结点的关键码都小于根结点的关键码；右子树（若存在）上的所有结点的关键码都大于根结点的关键码；左子树和右子树也是二叉搜索树。

typedef struct _NODE
{
    int data;
    struct _NODE* left;
    struct _NODE* right;
}NODE;

const NODE* find_data(const NODE* pNode, int data){
    if(NULL == pNode)
        return NULL;

    if(data == pNode->data)
        return pNode;
    else if(data < pNode->data)
        return find_data(pNode->left, data);
    else
        return find_data(pNode->right, data);       
}

4. Hash表

typedef struct _LINK_NODE
{
    int data;
    struct _LINK_NODE* next;
}LINK_NODE;

LINK_NODE* hash_find(LINK_NODE* array[], int mod, int data)
{
    int index = data % mod;
    if(NULL == array[index])
        return NULL;

    LINK_NODE* pLinkNode = array[index];
    while(pLinkNode){
        if(data == pLinkNode->data)
            return pLinkNode;
        pLinkNode = pLinkNode->next;
    }

    return pLinkNode;
}

分析：hash表因为不需要排序，只进行简单的归类，在数据查找的时候特别方便。查找时间的大小取决于mod的大小。mod越小，那么hash查找就越接近于普通查找；那么hash越大呢，那么hash一次查找成功的概率就大大增加。

一步一步写算法（之查找）