查找算法(顺序查找、二分法查找、二叉树查找、hash查找)

时间:2022-01-27 22:10:05

http://student.zjzk.cn/course_ware/data_structure/web/chazhao/chazhao9.3.1.5.htm


查找功能是数据处理的一个基本功能。数据查找并不复杂,但是如何实现数据又快又好地查找呢?前人在实践中积累的一些方法,值得我们好好学些一下。我们假定查找的数据唯一存在,数组中没有重复的数据存在。


(1)顺序查找(普通的数据查找)          

        设想有一个1M的数据,我们如何在里面找到我们想要的那个数据。此时数据本身没有特征,所以我们需要的那个数据可能出现在数组的各个位置,可能在数据的开头位置,也可能在数据的结束位置。这种性质要求我们必须对数据进行遍历之后才能获取到对应的数据。
[cpp]  view plain  copy
  1. int find(int *arr,int num,int value)  
  2. {  
  3.     if(NULL == arr || 0 == num)  
  4.         return -1;  
  5.   
  6.     for(int index = 0;index < num;index++){  
  7.         if(value == arr[index])  
  8.             return index;  
  9.     }  
  10.     return -1;  
  11. }  

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

(2)二分法查找                                           
        上面的数据没有任何特征,这导致我们的数据排列地杂乱无章。试想一下,如果数据排列地非常整齐,那结果会是什么样的呢?就像在生活中,如果平时不注意收拾整齐,那么找东西的时候非常麻烦,效率很低;但是一旦东西放的位置固定下来,所有东西都归类放好,那么结果就不一样了,我们就会形成思维定势,这样查找东西的效率就会非常高。
             那么, 对一个有序的数组,我们应该怎么查找呢?二分法就是最好的方法。
[cpp]  view plain  copy
  1. int binary_find(int *arr,int num,int value)  
  2. {  
  3.     if(NULL == arr || 0 == num)  
  4.         return -1;  
  5.       
  6.     int start = 0;  
  7.     int end = num - 1;  
  8.   
  9.     while(start <= end){  
  10.         int middle = start +((end - start)  >> 1);  
  11.         if(value == arr[middle])  
  12.             return middle;  
  13.         else if(value > arr[middle])  
  14.             start = middle + 1;  
  15.         else  
  16.             end = middle - 1;  
  17.     }  
  18.     return -1;  
  19. }  

分析
    上面我们说到普通的数据查找算法复杂度是o(n),那么我们可以用上面一样的方法判断一下算法复杂度。这种方法最少是1次,那么最多需要多少次呢?我们发现最多需要log(n+1)/log(2)即可。大家可以找个例子自己算一下,比如说7个数据,我们发现最多3次;如果是15个数据呢,那么最多4次,以此类推。明显,这种数据查找的效率要比前面的查找方法高很多。 优点:效率高,时间复杂度为O(logN);缺点:数据要是有序的,顺序存储。

(3)二叉树查找                                    
         上面的查找是建立在连续内存基础之上的,那么 如果是指针类型的数据呢?怎么办呢?那么就需要引入排序二叉树了。
        排序二叉树的定义很简单:(1)非叶子节点至少一边的分支非NULL;(2)叶子节点左右分支都为NULL;(3)每一个节点记录一个数据,同时左分支的数据都小于右分支的数据。可以看看下面的定义:
[cpp]  view plain  copy
  1. typedef struct _NODE{  
  2.     int data;  
  3.     struct _NODE* left;  
  4.     struct _NODE* right;  
  5. }NODE;  

代码
[cpp]  view plain  copy
  1. NODE* binarytree_find(NODE* pNode,int value)  
  2. {  
  3.     if(NULL == pNode)  
  4.         return NULL;  
  5.   
  6.     if(value == pNode->data)  
  7.         return pNode;  
  8.     else if(data < pNode->data)  
  9.         return binarytree_find(pNode->left,value);  
  10.     else  
  11.         return binarytree_find(pNode->right,value);  
  12. }  

(4)hash排序                                      
         方法(2)、(3)都是建立在完全排序的基础上,那么在没有建立折中基础上的排序呢?就是hash表。
        哈希表的定义如下:1)每个数据按照某种聚类运算归到某一大类,然后所有数据链成一个链表;2)所有链表的头指针形成一个指针数组。这种方法因为不需要完整排序,所以在处理中等规模数据的时候很有效。其中节点的定义如下:
[cpp]  view plain  copy
  1. typedef struct _NODE  
  2. {  
  3.     int data;  
  4.     struct _NODE* next;  
  5. }NODE;  

查找代码:
[cpp]  view plain  copy
  1. NODE* hash_find(NODE* arr[],int mod,int value)  
  2. {  
  3.     int index= data % mod;  
  4.     if(NULL == arr[index])  
  5.         return NULL;  
  6.       
  7.     NODE* pNode = arr[index];  
  8.     while(pNode){  
  9.         if(value == pNode->data)  
  10.             return pNode;  
  11.         pNode = pNode->next;  
  12.     }  
  13.     return pNode;  
  14. }  

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