文章目录
查找算法什么是查找算法：顺序查找：顺序表的顺序查找：链表的顺序查找：顺序查找的优点：顺序查找的缺点： 二分查找：二分查找的优点：二分查找的缺点： 索引查找：给顺序表创建索引表：索引表的顺序查找：索引表二分查找：给链表创建索引表：索引查找的优点：索引查找的缺点：索引查找的使用场景： 分块查找：分块查找的优点：分块查找的缺点： 二叉排序树和平衡二叉树：哈希表查找：设计哈函数的方法：直接定值法：数字分析法： 解决哈希值冲突的方法：哈希查找的优点：哈希查找的缺点：查找算法
什么是查找算法：
在一个数据序列中，查找某个数据是否存在或存在的位置，在实际开发过程中使用的频率非常高，例如对数据常见的操作有增、删、改、查，增加数据时需要查询新增加的数据是否重复，删除数据时需要先查询到数据所在位置再删除，修改数据时也需要先查询到被修改的数据在什么位置，查找算法在编程中重要性排列在第一位。
方便起见，下文的数据交换过程用swap（a，b）代替，就是常规的数据交换方式
顺序查找：
顺序表的顺序查找：
// 在顺序表中按照从前到后的顺序查找数据，如果找到则返回合法的下标，找不到则返回 -1int linear_search(int* arr,size_t len,int key){for(int i=0; i<len; i++){if(arr[i] == key)return i;}return -1;}
链表的顺序查找：
// 在顺序表中按照从前到后的顺序查找数据，如果找到则返回所在节点的地址，找不到则返回NULLNode* linear_search(Node* head,int key){for(Node* 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;while(left < right){int p = (left + right) / 2;if(arr[p] == key)return p;if(arr[p] > key)r = p;if(arr[p] < key)l = p+1;}return -1}// 函数递归实现int _binary_search(int* arr, int left, int right, int key){if(left >= right)return -1;int p = (left + right) / 2;if(arr[p] > key)return _binary_search(arr,left,p,key);if(arr[p] < key)return _binary_search(arr,p+1,right,key);return p;}int binary_search(int* arr, size_t len, int key){return _binary_search(arr,0,len,key);}
二分查找的优点：
查询速度快，时间复杂度：O(log2N)。
二分查找的缺点：
1、对数据的有序性有要求，必须要先排序完成。
2、对数据结构有要求，不适合链式表使用，因为无法计算出中间位置的数据。
索引查找：
索引查找是在索引表和主表(即线性表的索引存储结构)上进行的查找，但需要先建立索引表，索引表就类似图书的目录，能大提高查找效率。
给顺序表创建索引表：
typedef struct Student{int id; char name[20];char sex;short age;float src;}Student;Student stu[1000];typedef struct Index{int id; void* addr;}Index;Index* index[1000];void create_index(Student* stu,Index* index,size_t len){for(int i=0; i<len; i++){index[i].id = stu[i].id;index[i].addr = stu+i; } }
索引表的顺序查找：
// 它比直接查询原感受的跳转速度快，如果数据在内存中可以减少跳转的内存页数量，如果数据在机械硬盘中可以减少硬盘磁头的移动距离，如果使用stu[i]，i每增加一下，需要跳转sizeof(Student)个字节，如果使用index[i]，i每增加一下，只需要跳转sizeof(Index)个字节，。int linear_index(Index* index,size_t len,int id){for(int i=0; i<len; i++){if(index[i].id == id)return i;}}
索引表二分查找：
// 如果对原表直接排序，则每次需要交换sizeof(Student)，如果对索引表进行排序每次只需要交换sizeof(Index)个字节，数据的交换量对排序算法的程度影响非常大。void sort_index(Index* index,size_t len){for(int i=0; i<len-1; i++){int min = i;for(int j=i+1; j<len; j++){if(index[min].id > index[j].id)min = j;}if(i != min){Index tmp = index[min];index[min] = index[i];index[i] = tmp;}}}Student* binary_search(Index* index,size_t len,int id){int left = 0, right = len;while(left < right){int p = (left + right) / 2;if(index[p].id == id)return index[p].ptr;if(index[p].id > id)right = p;if(index[p].id < id)left = p+1;}return NULL;}
给链表创建索引表：
// 给链表创建了索引表后，再对索引表进行排序，就可以对链表进行二分查找的效果void create_index(Node* head,Index* index){int i = 0;for(Node* n=head; NULL!=n; n=n->next){index[i].id = ((Student*)n->ptr)->id;index[i].addr = n->ptr;}}
索引查找的优点：
1、对于顺序表的顺序查找，索引表可以缩小数据的查找范围。
2、对于顺序表的二分查找，索引表可以提高排序速度。
3、对于链表的可以在创建索引表后，进行二分查找。
索引查找的缺点：
使用了额外的存储空间创建索引表，是一种典型的用空间换取时间的策略。
索引查找的使用场景：
针对内存中的顺序表数据，索引查找提升的速度并不是特别大，而是对存储在机械硬盘中的数据的查找速度提升非常大，因此在数据库中索引查找使用的特别多。
分块查找：
先对数据进行分块，可以根据日期进行分块，可以对整形数据根据数据的最后一位分为10个分表，针对字符串数据可以根据第一个字母分为26个分表，然后再对这些分表进行二分查找、顺序查找，它是分治思想的具体实现。
分块查找的优点：
可以把海量数据进行分化，降低数据规模，从而提升查找速度。
分块查找的缺点：
操作比较麻烦，可能会有一定的内存浪费。
二叉排序树和平衡二叉树：
二叉排序树也叫二叉搜索树是根据数据的值进行构建的，然后进行前序遍历查找，它的查找原理还是二分查找，我在二叉搜索树中已经详细过，在此不再赘述。
平衡二叉树首先是一棵二叉排序树或二叉搜索树，二叉排序树在创建时，由于数据基本有序，会导致创建出的二叉排序树呈单枝状，或者随机数据的插入、删除导致二叉排序树左右失衡呈单枝状，就会导致二叉树排序的查询速度接近单向链表的O(N)；
平衡二叉树要求左右子树的高度差不超过1，这样就会让二叉排序树左右均匀，让二叉排序树的查找速度接近二分查找（要了解AVL树和红黑树的区别）。
哈希表查找：
在查找数据时需要进行一系列的比较运算，无论是顺序查找、二分查找、索引查找、这类的查找算法都是建立在比较的基础上的，但最理想的查找算法是不经过任何比较，一次存取就能查找到数据，那么就需要在存储位置和它的关键字之间建立一个确定的对应关系，使每个关键字和数据中的唯一的存储位置相对应。在查找时，根据对应关系找到给定的关键字所对应的数据，这样可以不经过比较可以直接取得所查找的数据。
我们称存储位置在关键字之间的对应关系为哈希函数，按这个思想建立的表为哈希表。
问题：假定有100万个0到255之间的随机数，然后输入一个0~255之间的整数，查询出该数一共出现了多少次。
#include <stdio.h>#include <stdlib.h>int arr[1000000];int cnts[256];// 最简单的哈希表int main(int argc,const char* argv[]){for(int i=0; i<1000000; i++){arr[i] = rand() % 256;}// 把数据会值作为数组cnts的下标(把要关键字与存储位置相对应)，直接定值法，H(key)=keyfor(int i=0; i<1000000; i++){cnts[arr[i]]++;}unsigned char num;printf("请输入一个整数(0~255)：");scanf("%hhu",&num);printf("%d\n",cnts[num]);return 0;}
以上例子有很大的局限性，很多时候无法使用数据的值作为数组的下标，因为可能会出现数据量少，但差值范围太大，会导致哈希表过大，实用性不强，所以就需要对关键字的值进行处理，处理方法就是哈希函数，进而缩小哈希表，然而设计哈希函数计算出的结果可能会出现重复，因此设计出合适的哈希函数、解决冲突问题是哈希表和哈希查找的关键，而且很多时候无法设计出哈希函数，比如浮点型数据，汉字字符串等很难设计出合适的哈希函数。
设计哈函数的方法：
直接定值法：
取关键字的值或某个线性函数作为k哈希地址：H(key) = key 或H(key)=a*key-b，但这种方法对数据有很高的要求。
数字分析法：
假设以关键字key为基数，并且哈希表中可能出现的数字全部知道，取关键字的某几位为哈希地址，例如学号：
12系、34为专业、56为年级、79为入学序号，因此H(key)=key%1000。
以上两种方法局限比较大，但计算出的哈希地址没有冲突的可能，以下方法：平方取中法、折叠法、除留余数法等方法对关键字的要求不要，但计算出的哈希地址可能会有冲突。
解决哈希值冲突的方法：
开方地址法再哈希法链地址法创建公共溢出区哈希查找的优点：
查找速度极快，时间复杂度能达到O(1)。
哈希查找的缺点：
1、局限性比较大，对数据的要求比较高。
2、设计哈希函数麻烦，没具体的设计哈希函数的方法，只是有一些大致的思路。
3、需要建立哈希表，占用了额外的空间。
