在线咨询
有事点这里
有事点这里
看不懂这篇文章?联系我们
("麦洛克菲"长期致力于内核与移动安全以及编程技术的推广与普及,我们更专业!)
如果想从事IT相关有竞争性的工作,欢迎报考麦洛克菲零基础班
作者:admin 时间:2016-10-31

第七章:查找

7.1折半查找

折半查找又叫二分查找,首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。

 

折半查找过程演示,如下图所示,表中元素按升序排列:

假如要查找一个数据253。那么首先查看表中中间位置(0+8)/2即位置为4的元素:53。因为25353要大,所以丢弃表中04的子表数据,剩下58的字表数据。然后再计算58的子表的中间位置(5+8)/26的位置的元素:101。因为253101的数据要大,所以丢掉56子表中的元素,剩下78子表的元素。然后找到78中间位置(7+8)/27所在位置的元素:253,二者相等,那么查找成功,即所在位置为7

 

假如要查找一个为3的数据。那么首先查看表中中间位置(0+8)/2即位置为4的元素:53。因为353要小,所以丢掉48之间的子表元素,保留03之间的子表元素。然后在计算03之间的中间元素(0+3)/21所在位置的元素:9。因为39要小,所以丢掉13之间子表元素,留下0位置的元素1,但31要大。所以整个表查完,没有找到该元素,查找失败。

 

下面是折半查找算法:

//a为存放数据的有序表,n为数据元素个数,k为要查找的元素

int BinSearch(int a[], int n, int k)

{

     int low, high, mid, find, i;

    

     find = 0;

     low = 0;

     high = n-1;

 

     while (low <= high && !find)

     {

         mid = (low + high)/2;

         if (a[mid] < k)

              low = mid + 1;

         else if (a[mid] > k)

              high = mid - 1;

         else

         {

              i = mid;

              find = 1;

         }

     }

     if (!find)

         i = -1;

     return i;

}

递归版本:

 

int IterBiSearch(int data[], const int x, int beg, int last)  

{  

    int mid = -1;  

    mid = (beg + last) / 2;  

    if (x == data[mid])  

    {  

        return mid;  

    }  

    else if (x < data[mid])  

    {  

        return IterBiSearch(data, x, beg, mid - 1);  

    }  

    else if (x > data[mid])  

    {  

        return IterBiSearch(data, x, mid + 1, last);  

    }  

    return -1;  

 

int BinSearch(int a[], int n, int k)

{

    return  IterBiSearch(a,k,0,n-1);

}

 

注意:折半查找必须满足两个条件:一,元素必须是连续存储;二,元素必须有序。时间复杂度:O(logn)

7.2Hash查找

Hash表用于存放key-value数据。比如一个学生的成绩,那么学生的学号可以当做key,成绩当做value,存放与hash表中。

Hash查找必须提供一个Hash函数,用于通过Key来计算数据存放在hash表中的位置。一般hash函数可以设计为key%N,其中Nhash表中元素的个数(一般为质数)。假如HASH表的大小为N,那么Hash函数为:

 

Hash(key)=key%N

 

当对于不同的两个key,计算出来的hash值可能相同,在相同的时候,就叫做hash冲突。解决hash冲突的方法不止一种,比如通过链式法解决,即将所有含有相同hash值的数据存放在同一个链表中,而将链表的头结点存放在HASH表中。

 

所谓hash查找,就是通过对应的key,按照hash函数,计算出数据在hash表中的位置。Hash查找的复杂度为O(1),所以具有较高的查找效率。

 

请编写一个高效率的函数来找出字符串中的第一个无重复字符。例如,"total"中的第一个无重复字符是’o’

 

int hash(char ch)

{

       return ch;

}

 

char find_first_norepeat_ch(const char *str)

{

       int hasharr[256]={0};

       char *s=(char *)str;

 

       while(*s)

       {

              hasharr[hash(*s)]++;

              s++;

       }

 

       s=(char *)str;

 

       while(*s)

       {

              if(hasharr[*s]==1)

              {

                     return *s;

              }

              s++;

       }

 

       return '\0';

 

}

7.3二叉搜索树查找

在第五章《树》,我们学习了什么叫做二叉排序树,即二叉搜索树。很多时候,我们也可以将数据存放在平衡二叉排序树里。那么如何使用它来进行查找数据呢?

 

struct _node

{

     int data;

     struct _node *left;

     struct _node *right;

} node, btree;

 

btree *search(btree *b, int x)

{

     if (b == NULL)

    {

         return NULL;

     }

    else

    {

         if (b->data == x)

        {

              return b;

         }

        else if (x < b->data)

        {

              return (search(b->left));

         }

       else

        {

              return (search(b->right));

         }

     }

}

平衡二叉排序树的查找复杂度为O(logn),因此也具有较高的查找效率。