Fork me on GitHub

查找算法


  1. 普通的查找算法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    int find(int array[],int length,int value)
    {
    if(NULL == array || 0 == length)
    return -1;

    for(int index = 0;index < length; index++)
    {
    if(value == array[index])
    {
    return index;
    }
    }

    return -1;
    }
> 时间复杂度:O(n)
  1. 二分查找

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    int binary_search(int array[],int length,int value)
    {
    if(NULL == array || 0 == length)
    return -1;

    int start = 0;
    int end = length - 1;
    int mid;
    while(start <= end)
    {
    mid = (start + end)/2;
    if(value == array[mid])
    return mid;
    else if(value > array[mid]){
    start = mid + 1;
    }else{
    end = mid - 1;
    }
    }

    return -1;
    }

    时间复杂度为:log2(n)

  2. 二叉排序树查找

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    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);

    }
  1. Hash查找

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    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])
    reutrn NULL;

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

    return pLinkNode;
    }
> 查找时间取决于mod的大小,mod越小就越接近于普通查找,越大,查找的成功概率越大
坚持原创技术分享,您的支持将鼓励我继续创作
-------------本文结束感谢您的阅读-------------
0%