六大查找算法 详细版讲解（C语言），硬核推荐！！！
查找，也可称检索，是在大量的数据元素中找到某个特定的数据元素而进行的工作。查找是一种操作。今天小编就带大家一起盘点一下。
顺序查找
基本思想：
顺序查找也称为线形查找，属于无序查找算法。从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于k的结点，表示查找失败。
复杂度分析：O(N)
unsigned int SeqSearch(int *pArray, int arraySize, int value){if (pArray != NULL && arraySize > 0){for (int i = 0; i < arraySize; i++){if (pArray[i] == value)return i;}return -1; // 给定内存中不存在 value}return -2; // 给定内存或查找范围无效}
二分查找
基本思想：
二分查找（Binary Search）算法，也叫折半查找算法，它的思想非常简单，在生活中随处可见（比如：猜字游戏），但这看似简单的算法，实际却没那么容易掌握透彻。
二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。
复杂度分析： O(log2n)
binarySearch(int a[], int n, int key){int low = 0;int high = n - 1;while(low<= high){int mid = (low + high)/2;int midVal = a[mid];if(midVal<key)low = mid + 1;else if(midVal>key)high = mid - 1;elsereturn mid;}return -1;}int main(){int i, val, ret;int a[8]={-32, 12, 16, 24, 36, 45, 59, 98};for(i=0; i<8; i++)printf("%d\t", a[i]);printf("\n请输人所要查找的元素：");scanf("%d",&val);ret = binarySearch(a,8,val);if(-1 == ret)printf("查找失败 \n");elseprintf ("查找成功 \n");return 0;}
插值查找
基本思想：
上面的二分查找，每次是从数组的中间位置查找的， 让我们把思维发散一下： 查找的位置一定要从中间开始查找吗？
打个比方： 我们在一本英文字典里面查找apple这个单词的时候， 你肯定不会从字典中间开始查找， 而是从字典开头部分开始翻，因为觉得这样的找法才是比较快的。
这给我提供了一个思路： 如果能在查找前较准确地预测关键字在数组中的位置的话，这样设计出的查找方法能比二分查找提高更多的性能！ 基于这种思想，我们设计了插值查找的算法。
插值查找其核心就在于插值的计算公式key-arr[low]/arr[high]-arr[low]。细看是不是key在整序列中的占比哟。
所以mid的计算公式为:（high-low）*（key-arr[low]）/（arr[high]-arr[low]）。对比折半查找的mid = （high-low）/2。
代码和折半查找一模一样，唯独mid的计算方式发生改变。
这样的好处在于，对表长较长，且关键字分分布比较均匀，插值查找算法的平均性能要比折半查找要好的多。但是 如果表中 关键字分布极端不均匀 那么插值查找还不如折半查找呢。
复杂度分析：O(log2(log2n))
#include<stdio.h>//插值查找-C语言实现//基本思路：二分查找改进版，只需改一行代码。// mid=low+(key-a[low])/(a[high]-a[low])*(high-low)int insertSearch(int *sortedSeq, int seqLength, int keyData);int main(){int array[] = { 1, 2, 3, 4, 15, 26, 37, 78, 99 };int location;int target = 27; //待查找的数值location = insertSearch(array, 9, target);if(location != -1){printf("已找到 位于 %d\n", location);}else{printf("找不到该数\n", location);}return 0;}int insertSearch(int *sortedSeq, int seqLength, int keyData){int low = 0, mid, high = seqLength - 1;while (low <= high){mid = low + (high-low)*(keyData - sortedSeq[low]) / (sortedSeq[high] - sortedSeq[low]);if (keyData < sortedSeq[mid]){high = mid - 1;//是mid-1，因为mid已经比较过了}else if (keyData > sortedSeq[mid]){low = mid + 1;}else{return mid;}}return -1;}
斐波那契查找
基本思想：
介绍这个算法之前首先要了解一个概念 - 斐波那契数列
斐波那契数列是一串按照F(0)=1，F(1)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）这一条件递增的一串数字：
1、1、2、3、5、8、13、21 ... ...
两个相邻项的比值会逐渐逼近0.618 —— 黄金分割比值。这个非常神奇的数列在物理，化学等各大领域上有相当的作用， 于是大家想： 能不能把它用在查找算法上嘞？？
于是就有了斐波那契算法， 裴波那契数列最重要的一个性质是每个数都等于前两个数之和（从第三个数字开始）。 也就是一个长度为f(n)的数组，它能被分成f(n-1)和f(n-2)这两半， 而f(n-1)又能被分为f(n-2)和f(n-3)这两半。。。直到分到1和1为止（f(1)和f(2)）。
斐波那契查找与折半查找很相似，他是根据斐波那契序列的特点对有序表进行分割的。他要求开始表中记录的个数为某个斐波那契数小1，及n=F(k)-1;
斐波那契查找的核心是：
1）当key=a[mid]时，查找成功；
2）当key<a[mid]时，新的查找范围是第low个到第mid-1个，此时范围个数为F[k-1] - 1个，即数组左边的长度，所以要在[low, F[k - 1] - 1]范围内查找；
3）当key>a[mid]时，新的查找范围是第mid+1个到第high个，此时范围个数为F[k-2] - 1个，即数组右边的长度，所以要在[F[k - 2] - 1]范围内查找。
复杂度分析：最坏情况下，时间复杂度为O(log2n)，且其期望复杂度也为O(log2n)。
void fibonacci(int *f) //构建斐波那契序列{f[0] = 1;f[1] = 1;for(int i = 2; i < MAXSIZE; ++i)f[i] = f[i - 2] + f[i - 1];}int fibonacci_search(int *a,int key,int n){int low = 0,high = n - 1;int mid = 0;int k = 0;int F[MAXSIZE];fibonacci(F);while(n > F[k] - 1) //计算出n在斐波那契中的位置++k;for(int i = n; i < F[k] - 1; ++i) //把数组补全，使用a[n-1]a[i] = a[high];while(low <= high){mid = low + F[k-1] - 1; //根据斐波那契数列进行黄金分割if(a[mid] > key){high = mid - 1;k = k - 1;}else if(a[mid] < key){low = mid + 1;k = k - 2;}else{if(mid <= high) //如果为真则找到相应的位置return mid;elsereturn -1;}}return -1;}int main(){int a[MAXSIZE] = {5,15,19,20,25,31,38,41,45,49,52,55,57};int k;printf("请输入要查找的数字:\n");scanf("%d",&k);int pos = fibonacci_search(a,k,13);if(pos != -1)printf("在数组的第%d个位置找到元素:%d\n",pos + 1,k);elseprintf("未在数组中找到元素:%d\n",k);return 0;}
二叉查找树查找
基本思想：
二叉查找树（BinarySearch Tree，也叫二叉搜索树，或称二叉排序树Binary Sort Tree）或者是一棵空树，或者是具有下列性质的二叉树：
1）若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2）若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3）任意节点的左、右子树也分别为二叉查找树。
复杂度分析：O(logn)
SearchTreeNode* _SearchTreeRemove(SearchTreeNode* root, SearchTreeType to_delete){if(root == NULL)return NULL;if(root->key > to_delete){root->lchild = _SearchTreeRemove(root->lchild,to_delete);}if(root->key < to_delete){root->rchild = _SearchTreeRemove(root->rchild,to_delete);}if(root->key == to_delete){// root 是叶子节点if(root->lchild == NULL && root->rchild == NULL){free(root);root = NULL;return NULL;}// root 非叶子节点 而且左子树为空,和右子树中最小元素交换,后删除找到的节点else if(root->lchild == NULL && root->rchild != NULL){SearchTreeNode* to_return = root->rchild;free(root);root = NULL;return to_return;}// root 非叶子节点,右子树为空,和左子树中最大元素交换,后删除找到的节else if(root->rchild == NULL && root->lchild != NULL){SearchTreeNode* to_return = root->lchild;free(root);root = NULL;return to_return;}// root 非叶子节点, 左子树中最大值和右子树中最大值 二选一交换 后删除找到的节else if(root->lchild != NULL && root->rchild != NULL){//采用赋值法//在左子树取最大值SearchTreeNode* max = root->lchild;SearchTreeNode* max_parent = root->lchild;while(max->rchild){max_parent = max;max = max->rchild;}root->key = max->key;//左子树是叶子节点(特殊情况)if(max_parent == max){free(max);max = NULL;root->lchild = NULL;}else{//不用判断将左子树的最大值至为空free(max_parent->rchild);max_parent->rchild = NULL;}return root;}}return root;}
哈希查找
哈希表（散列表）是直接通过关键字key得到要查找的记录的内存存储位置。
散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f(key)。
采用散列技术将记录存储在一块连续的存储空间中，这块连续的存储空间称为散列表或者哈希表。
整个散列过程分为两步：
因此散列技术既是一种存储方法也是一种查找方法，数据元素之间不存在逻辑关系。
最常用的方法是除留余数法，f(key)=key mod p（p小于等于散列表的长度m）。
复杂度分析：O(1)
typedef struct{int *elem;int count;}HashTable;int m=0;//初始化散列表int InitHashTable(HashTable *H){int i;m=HASHSIZE;H->count=m;H->elem=(int*)malloc(m*sizeof(int));for(i=0;i<m;i++)H->elem[i]=NULLKEY;return 1;}//散列函数int Hash(int key){return key%m;}//插入关键字进入散列表void InsertHash(HashTable *H,int key){int addr=Hash(key);while(H->elem[addr]!=NULLKEY)addr=(addr+1)%m;H->elem[addr]=key;}//散列表查找关键字int SearchHash(HashTable H,int key,int *addr){*addr=Hash(key);while(H.elem[*addr]!=key){*addr=(*addr+1)%m;if(H.elem[*addr]==NULLKEY||*addr==Hash(key)){return -1;}}return *addr;}int main(){int a[12]={12,67,56,16,25,37,22,29,15,47,48,34};HashTable H;int i;InitHashTable(&H);for(i=0;i<m;i++)InsertHash(&H,a[i]);printf("插入之后的哈希表为：");for(i=0;i<m;i++)printf("%d,",H.elem[i]);int addr,j;j=SearchHash(H,a[5],&addr);printf("搜索到a[5]的地址是：%d",j);}