七大查找算法

查找定义：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。

查找算法分类：

1）静态查找和动态查找；

注：静态或者动态都是针对查找表而言的。动态表指查找表中有删除和插入操作的表。

2）无序查找和有序查找。

无序查找：被查找数列有序无序均可；

有序查找：被查找数列必须为有序数列。

1、顺序查找

顺序查找又称为线性查找，是一种最简单的查找方法。适用于线性表的顺序存储结构和链式存储结构。

基本思路

从第一个元素m开始逐个与需要查找的元素x进行比较，当比较到元素值相同(即m=x)时返回元素m的下标，如果比较到最后都没有找到，则返回-1。

复杂度分析

查找成功时的平均查找长度为： ASL = 每个元素被查找的概率 * 总的元素的个数=1/n*(1+2+3+…+n) = (n+1)/2 ;
  当查找不成功时，需要n+1次比较，时间复杂度为O(n)，所以，顺序查找的时间复杂度为O(n)。
  
优缺点

缺点：是当n 很大时，平均查找长度较大，效率低；
优点：是对表中数据元素的存储没有要求。另外，对于线性链表，只能进行顺序查找。

int SeqSearch(int *a, int value, int len)
{
    for(int i=0; i<len; i++)
    {
        if(a[i] == value)
        {
            return i;
        }
    }

    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12

2、二分查找

二分查找，是一种在有序数组中查找某一特定元素的查找算法。

基本思路

用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。

复杂度分析

时间复杂度：折半搜索每次把搜索区域减少一半，时间复杂度为 O(logn) 。
空间复杂度：O(1)。

优缺点分析

当查找表不会频繁有更新、删除操作时，使用折半查找是比较理想的。如果查找表有较频繁的更新、删除操作，维护表的有序会花费比较大的精力，不建议使用该查找方式。

int BinarySearch(int * a, int value, int len)
{
    int low, high, mid;
    low = 0;
    high = len-1;
    mid = 0;

    while(low<=high)
    {
        mid = (high-low)/2;
        
        if(a[mid] == value)
        {
            return mid;
        }

        if(a[mid] > value)
        {
            high = mid - 1;
        }

        if(a[mid] < value)
        {
            low = mid + 1;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

递归实现

int BinarySearch1(int * a, int value, int low, int high)
{
    int mid = low + (high - low)/2;

    if(a[mid] == value)
    {
        return mid;
    }

    if(a[mid] < value)
    {
        BinarySearch1(a, value, mid+1, high);
    }

    if(a[mid] > value)
    {
        BinarySearch1(a, value, low, mid-1);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

3、插值查找

在二分查找中，每次都是从待查找序列的中间点开始查找，这样的做法在正确性上固然没什么问题，但假如要查找的值距离某个边界比较近，还从中间点开始查找，就有点浪费时间了。举个例子来说说明，假如在在一个{1,2…,100}的数组中，要查找88这个值，还一直采用和中间点比较的策略，就显得不太明智，因为明显可以明显从较为靠后的位置去检索。为了克服这种弊端， 引入了插值查找。

基本思路

插值查找是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的 查找方法，其核心就在于插值的计算公式 (key-array[low])/(array[high]-array[low])*(high-low)。简而言之，基于二分查找算法，将查找点的选择改进为自适应选择。

折半查找这种查找方式，不是自适应的（也就是说是傻瓜式的）。二分查找中查找点计算如下：
　　mid=(low+high)/2, 即mid=low+1/2*(high-low);
　　通过类比，我们可以将查找的点改进为如下：
　　mid=low+(key-a[low])/(a[high]-a[low])*(high-low)，
　　也就是将上述的比例参数1/2改进为自适应的，根据关键字在整个有序表中所处的位置，让mid值的变化更靠近关键字key，这样也就间接地减少了比较次数。

复杂度分析

时间复杂性：如果元素均匀分布，则O(log(logn))，在最坏的情况下可能需要 O(n)。
空间复杂度：O(1)。
  
优缺点分析

对于长度比较长、关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。

int InsertionSearch(int * a, int value, int low, int high)
{
    int mid = low+(value-a[low])/(a[high]-a[low])*(high-low);

    if(a[mid]==value)
    {
        return mid;
    }
    if(a[mid]>value)
    {
        return InsertionSearch(a, value, low, mid-1);
    }
    if(a[mid]<value)
    {
        return InsertionSearch(a, value, mid+1, high);
    }  
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

4、斐波那契查找

和前面的二分查找、插值查找相比，斐波那契查找是类似的，不过换了一种寻找mid点的方法。顾名思义，该种查找方法中，使用到了斐波那契数列，斐波那契数列的形式是：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…….（从第三个数开始，后边每一个数都是前两个数的和）。

基本思路
  在斐波那契数列中的元素满足这样的关系：F[k]=F[k-1]+F[k-2]，此处将这个数组稍微改一下，改成：（F[k]-1）=（F[k-1]-1）+（F[k-2]-1）+1，图示如下：
    

通过上面的图，应该就可以看出为什么要这样分割数组了，因为要找出一个中间mid值，以便将数组按斐波那契数列的规律，分割成两部分。
复杂度分析
  最坏情况下，时间复杂度为O(logn)，且其期望复杂度也为O(logn)。

    F[1]=1;
    for(int i=2;i<max_size;++i)
        F[i]=F[i-1]+F[i-2];
}

/*定义斐波那契查找法*/  
int FibonacciSearch(int *a, int n, int key)  //a为要查找的数组,n为要查找的数组长度,key为要查找的关键字
{
  int low=0;
  int high=n-1;
  
  int F[max_size];
  Fibonacci(F);//构造一个斐波那契数组F 

  int k=0;
  while(n>F[k]-1)//计算n位于斐波那契数列的位置
      ++k;

  int  * temp;//将数组a扩展到F[k]-1的长度
  temp=new int [F[k]-1];
  memcpy(temp,a,n*sizeof(int));

  for(int i=n;i<F[k]-1;++i)
     temp[i]=a[n-1];
  
  while(low<=high)
  {
    int mid=low+F[k-1]-1;
    if(key<temp[mid])
    {
      high=mid-1;
      k-=1;
    }
    else if(key>temp[mid])
    {
     low=mid+1;
     k-=2;
    }
    else
    {
       if(mid<n)
           return mid; //若相等则说明mid即为查找到的位置
       else
           return n-1; //若mid>=n则说明是扩展的数值,返回n-1
    }
  }  
  delete [] temp;
  return -1;
}

int main()
{
    int a[] = {0,16,24,35,47,59,62,73,88,99};
    int key=100;
    int index=FibonacciSearch(a,sizeof(a)/sizeof(int),key);
    cout<<key<<" is located at:"<<index;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

5、树表查找

二叉排序树是最简单的树表查找算法，该算法需要利用待查找的数据，进行生成树，确保树的左分支的值小于右分支的值，然后在就行和每个节点的父节点比较大小，然后再进行查找。

二叉排序树性质
  二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
   1>若左子树不空，则左子树上所有结点的键值均小于或等于它的根结点的键值。
   2>若右子树不空，则右子树上所有结点的键值均大于或等于它的根结点的键值。
   3>左、右子树也分别为二叉排序树。

二叉排序树中序遍历
  二叉排序树有不同的遍历方式，中序遍历的结果比较直观，是一个有序的序列。二叉树示例如下：
  
  二叉树上中序遍历的方式是：左节点、当前节点、右节点。该二叉树的遍历结果为：1、3、4、6、7、8、10、13、14。

二叉树查找步骤
  先创建二叉排序树，再进行查找。

二叉树查找实现

struct BTreeNode
{
    int data;
    BTreeNode * left;
    BTreeNode * right;
};
//二叉树创建
void create(BTreeNode* & Node)
{
    int  data = 0;
    
    cin>>data;

    if(data > 0)
    {
        Node = new BTreeNode;
        Node->data = data;
        create(Node->left);
        create(Node->right);
    }
    else
    {
        Node = NULL;
        return;
    }
}
//二叉搜索树查找
BTreeNode * SearchTree(BTreeNode * Node, int data)
{
    if(Node == NULL)
    {
        return NULL;
    }

    if(Node->data == data)
    {
        return Node;
    }

    if(Node->data > data)
    {
        return SearchTree(Node->left, data);
    }
    else
    {
        return SearchTree(Node->right, data);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

6、分块查找

分块查找又称索引顺序查找，它是顺序查找的一种改进方法。

算法思想：将n个数据元素"按块有序"划分为m块（m ≤ n）。每一块中的结点不必有序，但块与块之间必须"按块有序"；即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素，……

算法流程：
　　step1 先选取各块中的最大关键字构成一个索引表；
　　step2 查找分两个部分：先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中；然后，在已确定的块中用顺序法进行查找。

7、哈希查找

什么是哈希表（Hash）？

我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数， 也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素"分类"，然后将这个元素存储在相应"类"所对应的地方。但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了"冲突"，换句话说，就是把不同的元素分在了相同的"类"之中。后面我们将看到一种解决"冲突"的简便做法。
总的来说，"直接定址"与"解决冲突"是哈希表的两大特点。
　　
什么是哈希函数？

哈希函数的规则是：通过某种转换关系，使关键字适度的分散到指定大小的的顺序结构中，越分散，则以后查找的时间复杂度越小，空间复杂度越高。

算法思想：哈希的思路很简单，如果所有的键都是整数，那么就可以使用一个简单的无序数组来实现：将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。这是对于简单的键的情况，我们将其扩展到可以处理更加复杂的类型的键。

算法流程：

1）用给定的哈希函数构造哈希表；
2）根据选择的冲突处理方法解决地址冲突；

常见的解决冲突的方法：拉链法和线性探测法。详细的介绍可以参见：浅谈算法和数据结构: 十一 哈希表。

3）在哈希表的基础上执行哈希查找。
　　哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制，那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为O(1)；如果没有时间限制，那么我们可以使用无序数组并进行顺序查找，这样只需要很少的内存。哈希表使用了适度的时间和空间来在这两个极端之间找到了平衡。只需要调整哈希函数算法即可在时间和空间上做出取舍。
　　
复杂度分析：

单纯论查找复杂度：对于无冲突的Hash表而言，查找复杂度为O(1)（注意，在查找之前我们需要构建相应的Hash表）。

使用Hash，我们付出了什么？

我们在实际编程中存储一个大规模的数据，最先想到的存储结构可能就是map，也就是我们常说的KV pair，经常使用Python的博友可能更有这种体会。使用map的好处就是，我们在后续处理数据处理时，可以根据数据的key快速的查找到对应的value值。map的本质就是Hash表，那我们在获取了超高查找效率的基础上，我们付出了什么？

Hash是一种典型以空间换时间的算法，比如原来一个长度为100的数组，对其查找，只需要遍历且匹配相应记录即可，从空间复杂度上来看，假如数组存储的是byte类型数据，那么该数组占用100byte空间。现在我们采用Hash算法，我们前面说的Hash必须有一个规则，约束键与存储位置的关系，那么就需要一个固定长度的hash表，此时，仍然是100byte的数组，假设我们需要的100byte用来记录键与位置的关系，那么总的空间为200byte,而且用于记录规则的表大小会根据规则，大小可能是不定的。