算法（查找算法---二分查找/索引查找/哈希表查找）

二、查找算法

什么是查找算法：

在一个数据序列中，查找某个数据是否存在或存在的位置，在实际开发过程中使用的频率非常高，例如对数据常见的操作有增、删、改、查，增加数据时需要查询新增加的数据是否重复，删除数据时需要先查询到数据所在位置再删除，修改数据时也需要先查询到被修改的数据在什么位置，查找算法在编程中重要性排列在第一位。

顺序查找：

顺序表的顺序查找：

//  从顺序表中从前往后查找数据，找到返回下标，找不到返回-1
int order_search(int* arr,size_t len,int key)
{for(int i=0; i<len; i++){if(key == arr[i]) return i;}return -1;
}

链表的顺序查找：

ListNode* order_search(ListNode* head,int key)
{for(ListNode* n=head; NULL!=n; n=n->next){if(n->data == key) return n;}return NULL;
}

顺序查找的优点：

• 对待查找的数据没有有序性的要求，无论是否有序都可以顺序查找

• 对待查找的数据的存储方式也没有要求，无论是顺序表还是链表都可以顺序查找

顺序查找的缺点：

• 相比于其他查找算法速度要慢，最优时间复杂度 O(1) 最差O(N) 平均O(N)

二分查找：

数据序列必须有序，然后关键字key与中间数据比较，如果相等则立即返回，如果key小于中间数据，则只需要在中间数据左边继续查找即可，如果key大于中间数据，则只需要在中间数据右边继续查找即可，重复该步骤，直到找到关键字，或中间数据左右两边为空，则查找失败。

//  循环实现  查找前已有序
int binary_search(int* arr,size_t len,int key)
{int left = 0, right = len-1;while(left <= right){int p = (left + right)/2;if(arr[p] == key)return p;if(key < arr[p])right = p-1;if(key > arr[p])left = p+1;}return -1;
}
​
//  递归实现
int _binary_search(int* arr,size_t len,int key,int l,int r)
{if(l > r) return -1;int p = (l+r)/2;if(key < arr[p])return _binary_search(arr,len,key,l,p-1);if(key > arr[p])return _binary_search(arr,len,key,p+1,r);return p;
}
​
int binary_search(int* arr,size_t len,int key)
{return _binary_search(arr,len,key,0,len-1);
}

二分查找的优点：

查询速度快，时间复杂度：O(log2N)。

二分查找的缺点：

• 对待查找的数据有序性有要求，必须先排序才能二分查找

• 对数据存储结构有要求，不适合链式表中直接使用，因为无法快速地访问中间位置，以及快速地让左右标杆位置进行移动

索引查找：

索引查找是在索引表和主表(即线性表的索引存储结构)上进行的查找，但需要先建立索引表，索引表就类似图书的目录，能大提高查找效率。

给顺序表创建索引表：

typedef struct Stduent
{int id;char name[20];char sex;short age;float score;
}Student;
​
Student stu[10000]; //  主表
​
//  索引表元素结构
typedef struct Index
{int id;void* addr;
}Index;
​
//  索引表
Index indexs[10000];
​
//  对主表与索引表之间建立索引
void create_index(Student* stu,Index* indexs,size_t len)
{for(int i=0; i<len; i++){indexs[i].id = stu[i].id;indexs[i].addr = stu+i;}
}
//  注意：建立索引表后，后面使用索引查找的是索引表，再通过找到的索引表中记录的主表元素的位置信息，来最终找到待查找的数据元素
//  注意：索引表如何建立索引，根据实际需求来选择

索引表的顺序查找：

//  它比直接查询数据的主表的跳转速度要快，如果使用stu[i]查找，i每加1，要跳转过sizeof(Student)个字节数，如果使用索引表indexs[i]查询，i每加1，则只需要跳转sizeof(Index)个字节数，比主表跳转字节数要少。
//  如果主表的数据不存在内存而是存储在磁盘上，而索引表是建立在内存中，通过索引表访问效率、速度远高于访问磁盘的主表
int order_index_search(Index* indexs,size_t len,int id)
{for(int i=0; i<len; i++){if(indexs[i].id == id)return i;}/*for(int i=0; i<len; i++){if(stu[i].id == id)return i;}*/
}

索引表二分查找：

//  需要对索引表先排序
//  对索引表排序的效率和速度要远比直接对主表的排序要快
void sort_index(Index* indexs,size_t len)
{for(int i=0; i<len-1; i++){int min = i;for(int j=i+1; j<len; j++){if(indexs[j].id < indexs[min].id)min = j;}if(min != i){Index temp = indexs[min];indexs[min] = indexs[i];indexs[i] = temp;}}
}
​
//  对索引表进行二分查找
//  因为索引表已经重新排序了，而主表没有排序过，所以不能返回在索引表中找到元素的下标，该下标与主表对应元素的下标很可能不一致了，所以需要直接返回主表对应元素的地址
Student* binary_index_search(Index* indexs,size_t len,int id)
{int l = 0, r = len-1;while(l <= r){int p = (l + r)/2;if(indexs[p].id == id)return indexs[p].addr;if(id < indexs[p].id)r = p-1;if(id > indexs[p].id)l = p+1;}return NULL;
}

给链表创建索引表：

//  给链表head创建一张顺序的索引表 表中的元素是ListNode* 用来指向链表中的节点 
//  返回值是返回索引表首地址，len_i输出型参数，返回索引表中元素的个数
ListNode** create_index_list(ListNode* head,size_t* len_i)
{if(NULL == head || NULL == len_i) return NULL;//  索引表的长度*len_i = 0;ListNode** indexs = NULL;//  遍历链表head 给每个节点建立普通索引for(ListNode* n=head; NULL!=n; n=n->next){//  申请索引表元素ListNode*的内存indexs = realloc(indexs,sizeof(ListNode*)*(*len_i+1));//  让索引表中的最后一个元素指向对应的链表节点indexs[(*len_i)++] = n;}//  对索引表进行排序，交换索引表中指针的指向for(int i=0; i<(*len_i)-1; i++){int min = i;for(int j=i+1; j<*len_i; j++){if(indexs[j]->data < indexs[min]->data)min = j;}if(min != i){//  交换索引表中指针的指向 不修改链表ListNode* temp = indexs[min];indexs[min] = indexs[i];indexs[i] = temp;}}
}
​
//  链表的二分查找，本质上是对顺序的索引表进行二分
int binary_list_index_search(ListNode** indexs,size_t len,int key)
{int l = 0, r = len - 1;while(l <= r){int p = (l + r)/2;if(indexs[p]->data == key)return p;if(key < indexs[p])r = p-1;if(key > indexs[p])l = p+1;}return -1;
}

索引查找的优点：

• 对于顺序表的顺序查找，索引查找可以缩短数据的查找跳转范围

• 对于顺序表的二分查找，通过排序索引表也能提高排序的速度

• 对于链式表，可以先建立顺序的索引表后，进行之前无法实现的二分查找了

索引查找的缺点：

• 使用了额外的存储空间来创建索引表，是一种典型的以空间换时间的算法策略

索引查找的使用场景：

• 如果针对的是内存中的顺序表中的数据，通过索引查找提升的速度和效率其实并不是很明显，毕竟内存的运算速度很快

• 但是对于存储在机械硬盘上的数据，通过在内存中建立对应硬盘数据的索引表，访问起来提升的效率就很多了，因此在一些常用的数据库中的索引查找使用非常多

分块查找：

先对数据进行分块，可以根据日期进行分块，可以对整形数据根据数据的最后一位分为10个分表，针对字符串数据可以根据第一个字母分为26个分表，然后再对这些分表进行二分查找、顺序查找，它是分治思想的具体实现。

分块查找的优点：

可以把海量数据进行分化，降低数据规模，从而提升查找速度。

分块查找的缺点：

操作比较麻烦，可能会有一定的内存浪费。

二叉排序树和平衡二叉树：

二叉排序树也叫二叉搜索树是根据数据的值进行构建的，然后进行前序遍历查找，它的查找原理还是二分查找，我在二叉搜索树中已经详细过，在此不再赘述。

平衡二叉树首先是一棵二叉排序树或二叉搜索树，二叉排序树在创建时，由于数据基本有序，会导致创建出的二叉排序树呈单枝状，或者随机数据的插入、删除导致二叉排序树左右失衡呈单枝状，就会导致二叉树排序的查询速度接近单向链表的O(N)；

平衡二叉树要求左右子树的高度差不超过1，这样就会让二叉排序树左右均匀，让二叉排序树的查找速度接近二分查找（要了解AVL树和红黑树的区别）。

哈希表查找：Hash

在查找数据时需要进行一系列的比较运算，无论是顺序查找、二分查找、索引查找、这类的查找算法都是建立在比较的基础上的，但最理想的查找算法是不经过任何比较，一次存取就能查找到数据，那么就需要在存储位置和它的关键字之间建立一个确定的对应关系，使每个关键字和数据中的唯一的存储位置相对应。在查找时，根据对应关系找到给定的关键字所对应的数据，这样可以不经过比较可以直接取得所查找的数据。

我们称存储位置在关键字之间的对应关系为哈希函数，按这个思想建立的表为哈希表。

设计哈函数的方法：

直接定值法：

取关键字的值或某个线性函数作为k哈希地址：H(key) = key 或H(key)=a*key-b，但这种方法对数据有很高的要求。

问题：假设有10000个范围在0~255之间的随机整数，请任意输入0~255之间的一个整数，帮查询该整数总共出现了多少次？

#include <stdio.h>
#include <stdlib.h>
​
int main(int argc,const char* argv[])
{int arr[10000] = {};
​for(int i=0; i<10000; i++){arr[i] = rand() % 256;}
​//  建立哈希表int hash[256] = {};//  通过直接定值法 建立哈希函数for(int i=0; i<10000; i++){hash[arr[i]]++;}
​unsigned char num = 0;printf("请输入:");scanf("%hhu",&num);
​printf("次数:%d\n",hash[num]);
}  
​

时间复杂度：O(1)

但是有很大的局限性，因为很多数据是无法直接用做数组的下标的，其次可能会出现数据量少，但是数据值的差值较大，导致哈希表长度过大，造成内存浪费

数字分析法：

分析数据的特点设计哈希，常用方法是找到最大最小值，最大值-最小值+1 确定哈希表的长度，通过 数据-最小值 访问哈希表下标

以上两种方法局限比较大，但计算出的哈希地址没有冲突的可能，以下方法：平方取中法、折叠法、除留余数法等方法对关键字的要求不要，但计算出的哈希地址可能会有冲突。称为哈希冲突

解决哈希值冲突的方法：

• 开方地址法

• 再哈希法

• 链地址法

• 创建公共溢出区

哈希查找的优点：

查找速度极快，时间复杂度能达到O(1)。

哈希查找的缺点：

1、局限性比较大，对数据的要求比较高。

2、设计哈希函数麻烦，没具体的设计哈希函数的方法，只是有一些大致的思路。

3、需要建立哈希表，占用了额外的空间。

Hash函数的应用：MD5、SHA-1都属于Hash算法