文章目录

查找1、什么是查找？2、查找算法如何分类3、如何评估查找算法的效率4、具体算法类型及其实现4.1 顺序查找（线性查找）4.2 二分查找（折半查找）4.3 插值查找（优化二分查找）4.4 Fibonacci查找（斐波那契数列）4.5 树表查找（树结构）4.5.1 二叉树查找4.5.2 平衡查找树之2-3查找树（2-3 Tree）4.5.3 平衡查找树之红黑树（Red-Black Tree）4.5.4 B树和B+树（B Tree/B+ Tree） 4.6 哈希查找（哈希函数）4.7 分块查找（改进的顺序查找、折半查找）

查找

1、什么是查找？

一个比较有用的信息就是：查找算法没有稳定性问题、查找算法的设计需要结合特定的数据结构以及一些操作来考虑。

2、查找算法如何分类

查找算法按照查找表是否有序的情况，可以分为：

无序查找：被查找数列有序无序均可；有序查找：被查找数列必须为有序数列。

按照对查找表施加的动作，可以分为：

静态查找：只对查找表进行查找操作；动态查找：对查找表进行查找操作，还可以对查找表数据进行修改。

3、如何评估查找算法的效率

衡量查找算法的效率，依据是平均查找长度（Average Search Length，ASL），指查找过程中关键字的平均比较的次数。使用公式表示：

4、具体算法类型及其实现

4.1 顺序查找（线性查找）

顾名思义，就是按照查找表，从左到右或者从右到左顺序查找。 java代码：

public static int sequenceSearch(int a[], int value, int n) { for(int i=1;i<n;i++) { if(a[i]==value) { return i; } } return -1; }

复杂度分析：时间复杂度O(n) ASL = 1/n(1+2+3+…+n) = (n+1)/2

4.2 二分查找（折半查找）

二分查找也叫折半查找，就是通过将key（要查找的值）和已经排好序的查找表中的中间值比较，根据结果来判断：

等于该中间值，则查找到，返回位置mid大于该中间值，则在左半部分继续类似的查找小于该中间值，则在右半部分继续类似的查找

java代码：

/* 迭代版*/ public static int binarySearch(int []a,int value,int n){ int low=0; int high=n-1; int mid=0; while(low<high){ mid = low+(high-low)*1/2;//每次都是比较中间的值 if(a[mid] == value) {//等于 return mid; } if(a[mid] > value) {//大于，则在左半部分查找 high = mid - 1;//只改变high } else {//反之在右半部分查找 low = mid + 1;//只改变low } } return -1; //查找失败，return low，low表示此时如果要执行插入，插入的位置 } /*递归版*/ public int binarySearch(int[] a, int target, int low, int high) { if (low > high) { return low; //查找失败，low表示此时如果要执行插入，插入的位置 int mid = low + (high - low) / 2;//中间值 if (a[mid] > target) {//大于，查找左半部分 return binarySearch(a,target,low,mid-1); } else if (a[mid] < target) {//小于，查找右半部分 return binarySearch(a,target,mid+1,high); } else { return mid;//查找成功 } }

复杂度分析：时间复杂度为O(log2n)，对比顺序查找，对于一个有1024个元素的数组，在最坏的情况下，二分查找法只需要比较log2n + 1= 11次，而在最坏的情况下线性查找要比较1023次。

注意事项

查找表是有序的！对于静态查找，该算法的效率不错。但是如果是动态查找，因为查找过程需要进行插入或者删除操作，这就要求每次查找前需要数据重新排序，从而导致效率降低！使用high+low时要注意，如果是int类型，要注意是否溢出，即超过Integer.MAX_VALUE

4.3 插值查找（优化二分查找）

比较简单的理解，就是我们不再使用二分比例（1/2），而是根据要查找的数据其大小在整个数列的大概比例从而判断其左半部分或者右半部分的范围。如1、2、3、4......10——a0到a9，现在要查找的数是8，low=0，high=9；（8-1）/（10-1）=7/9，则mid = low+（high-low）*7/9=0+7=7，所以我们应该在[7,9]或者[0,6]的范围找，而不是[0,4],[5,9]

//二分查找 mid = low+(high-low)*1/2;//每次都是比较中间的值，比例是1/2 //插值查找 mid = low + (high-low) * (value-a[low]) / (a[high]-a[low]);//根据数据，确定比例 public static int insertionSearch(int a[], int value, int n) { int low = 0; int high = n-1; int mid = 0; while (low <= high) { mid = low + (high-low) * (value-a[low]) / (a[high]-a[low]); if(a[mid] == value) { return mid; } if(a[mid] > value) { high = mid - 1; } else { low = mid + 1; } } return -1; }

复杂度分析：查找成功或者失败的时间复杂度均为O(log2(log2n))。 注意事项

查找表依旧需要有序查找的效率很依靠数据分布的均匀性。关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。

4.4 Fibonacci查找（斐波那契数列）

1、Fibonacci数列是什么？ 斐波那契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、····，在数学上，斐波那契被递归方法如下定义：F(1)=1，F(2)=1，F(n)=f(n-1)+F(n-2) （n>=2）。该数列越往后相邻的两个数的比值越趋向于黄金比例值（0.618）。 2、Fibonacci查找 斐波那契查找也叫做黄金分割法查找，它也是根据折半查找算法来进行修改和改进的。因为二分查找或者插值查找都要用到除法，而Fibonacci查找只需要用到加法减法。 3、算法是如何实现查找的？

建立斐波那契数列F（n），如 1 1 2 3 5 8 13…根据查找表（data数组）的长度，找到略大于data.length的F（n）,如data的长度为10，则找到F（7）=13；建立长度为F（n）的临时查找表temp[F(n)],将data的值一一复制到temp对应位置，temp中剩下的元素用data中最后的元素填充。如temp[13],前10个数对应data里边的数，temp[10]、temp[11]，temp[12]都赋值为temp[9]利用查找规则，进行查找。

查找规则： F[n]个元素分割为前半部分F[n-1]个元素，后半部分F[n-2]个元素，找出要查找的元素在那一部分并递归，直到找到。 图解：

java代码

/** * 创建斐波那契数列 * @return 斐波那契数列 */ private static int[] fibonacci(){ int n = 30;//默认创建100项 int []f = new int[n]; f[0]=1; f[1]=1; for(int i=2;i<n;i++){ f[i]=f[i-1]+f[i-2]; } return f; } private static int fibonacciSearch(int []data,int value) { int []f = fibonacci();//获取斐波那契数列 int low =0,mid=0; int len = data.length; int high = len-1; //1、寻找f(n)略大于数组长度 int k=0; while(len>f[k]){ k++; } //2、创建临时数组 int []temp = new int[f[k]]; for(int i=0;i<f[k];i++){ if(i<len) temp[i]=data[i]; else temp[i]=data[len-1]; } /* for(int i:temp){ System.out.print(i+" "); } System.out.println();*/ //3、开始查找 while(low<=high){ mid = low+f[k-1]-1; if(temp[mid]<value){//右半部分 low = mid+1; k = k-2;//f(n)=f(n-1)+f(n-2); }else if(temp[mid]>value){//左半部分 high = mid-1; k = k-1; }else{ if(mid<=high)//查找到了 return mid; else return high;//但是位于temp填充的部分，等于high } } return -1;//查找失败。 }

复杂度分析 同样，斐波那契查找的时间复杂度还是O(log2n)，但是与折半查找相比，斐波那契查找的优点是它只涉及加法和减法运算，而不用除法，而除法比加减法要占用更多的时间，因此，斐波那契查找的运行时间理论上比折半查找小，但是还是得视具体情况而定。

4.5 树表查找（树结构）

4.5.1 二叉树查找

步骤 1、构建二叉查找树 将需要查找的数据建立二叉树，小于双亲结点的为左子树，大于等于双亲结点的为右子树。 2、根据要查找的树与结点值比较，大于当前结点则比较右子树，小于当前结点则比较左子树，等于则返回位置

以上步骤是静态查找的步骤。当要插入数据或者删除数据的时候，我们还需要实现插入结点和删除结点同时调整二叉树。

所以我们需要实现

创建二叉树——creatTree（）查找二叉树——binaryTreeSearch()插入结点——insertNode（）删除节点——deleteNode（）

C++代码实现

#include<cstdio> #include<cstdlib> #define null NULL typedef struct Node{ int value; struct Node *parent; struct Node *left; struct Node *right; }treeNode; //中序遍历 void displayTree(treeNode* node){ if(node == null) return; if(node->left != null){ displayTree(node->left); } printf("%d ",node->value); if(node->right != null){ displayTree(node->right); } } //插入结点 void insertNode(treeNode *node,treeNode* inode){ if(inode->value>=node->value&&node->right!=null){ //如果大于等于该结点，而该结点右子树不空则递归插入 insertNode(node->right,inode); return; } if(inode->value<node->value&&node->left!=null){ //如果小于该结点，而该结点左子树不空则递归插入 insertNode(node->left,inode); return; } if(inode->value>=node->value&&node->right==null){ //如果大于该结点，而该结点右子树空则插入 node->right = inode; inode->parent = node; } if(inode->value<node->value&&node->left==null){ //如果大于该结点，而该结点右子树空则插入 node->left = inode; inode->parent = node; } } //创建二叉查找树 void createBinaryTree(treeNode **root,int array[],int size){ *root = (treeNode*)malloc(sizeof(treeNode)); (*root)->value = array[0];//默认以第一个元素为根结点。 (*root)->right = null; (*root)->left = null; (*root)->parent = null; for(int i=1;i<size;i++){ treeNode *child = (treeNode*)malloc(sizeof(treeNode)); child->value=array[i]; child->right =child->left= null; insertNode(*root,child);//插入结点 } } //查找value，成功则返回该结点 treeNode* binaryTreeSearch(treeNode *node,int value){ if(node->value==value) return node; else if(node->value>value){ if(node->left!=null) return binaryTreeSearch(node->left,value); else return null; }else{ if(node->right!=null) return binaryTreeSearch(node->right,value); else return null; } } //查找以node为节点的树中上是否存在vlaue的节点,parent为查找到的节点的父节点。 //dir为1表示parent节点的左节点为查找结果；为2表示parent节点的右节点为查找结果 treeNode* searchTreeWithParent(treeNode* node, treeNode** parent, int* dir, int value){ if(node->value == value){ return node; }else if(node->value > value){ if(node->left != NULL){ *dir = 1; *parent = node; return searchTreeWithParent(node->left, parent, dir, value); }else{ return NULL; } }else{ if(node->right != NULL){ *dir = 2; *parent = node; return searchTreeWithParent(node->right, parent, dir, value); }else{ return NULL; } } } //从以root为根节点的树中删除值为value的节点 void deleteNode(treeNode** root, int value){ treeNode* parent = NULL; int dir = -1; treeNode* deleteNode = searchTreeWithParent(*root,&parent,&dir,value); if(deleteNode == NULL){ printf("%s\n", "node not found"); }else{ if(deleteNode->left == NULL && deleteNode->right == NULL){ if(parent != NULL){ if(dir == 1) parent->left = NULL; else parent->right = NULL; }else{ *root = NULL; } }else if(deleteNode->left != NULL && deleteNode->right == NULL){ if(parent != NULL){ if(dir == 1) parent->left = deleteNode->left; else parent->right = deleteNode->left; }else{ *root = deleteNode->left; } }else if(deleteNode->left == NULL && deleteNode->right != NULL){ if(parent != NULL){ if(dir == 1) parent->left = deleteNode->right; else parent->right = deleteNode->right; }else{ *root = deleteNode->right; } }else{ insertNode(deleteNode->left,deleteNode->right); if(parent != NULL){ if(dir == 1) parent->left = deleteNode->left; else parent->right = deleteNode->left; }else{ *root = deleteNode->left; } } free(deleteNode); deleteNode = NULL; } } //删除以node为根结点的树 void deleteTree(treeNode* node){ if(node == NULL) return; if(node->left != NULL){ deleteTree(node->left); } if(node->right != NULL){ deleteTree(node->right); } if(node->left == NULL && node->right == NULL){ free(node); node = NULL; } } int main(){ int array[12] = {4,1,45,78,345,33,55,23,12,3,6,21}; //创建根结点 treeNode *root = NULL; //创建二叉树 createBinaryTree(&root, array, 12); printf("the tree is:"); //打印构建的二叉树 displayTree(root); printf("\n"); int value = 78; printf("search value %d:",value); treeNode*objNode = null; if((objNode=binaryTreeSearch(root,value))!= NULL){ printf("%s\n","exist"); }else{ printf("%s\n","not exist"); } printf("delete value:%d ",value); //删除value这个值的结点 deleteNode(&root,value); printf("\n"); printf("the tree is :"); //重新打印二叉树 displayTree(root); printf("\n"); //删除整棵树 deleteTree(root); return 0; }

复杂度分析 它和二分查找一样，插入和查找的时间复杂度均为O(logn)，但是在最坏的情况下仍然会有O(n)的时间复杂度。原因在于插入和删除元素的时候，树没有保持平衡。所以我们期望在最坏的情况下仍然有较好的时间复杂度，后来设计了平衡查找树。最坏的情况如（b）

4.5.2 平衡查找树之2-3查找树（2-3 Tree）

4.5.3 平衡查找树之红黑树（Red-Black Tree）

4.5.4 B树和B+树（B Tree/B+ Tree）

4.6 哈希查找（哈希函数）

建立一个Hash表，查找表就是哈希表，如果是无冲突的哈希表，那么能够实现时间复杂度为O（1）的查找。关于Hash表的描述，请参考HashTable详解

4.7 分块查找（改进的顺序查找、折半查找）

属于顺序查找，分块查找又称索引顺序查找，它是折半查找和顺序查找的改进方法

1、将数据分块，使得分成的数据块——块内无序，块间有序（第一块的最大关键字必须小于第二块的最小关键字，依次类推）2、 根据块的最大关键字，构建索引表。图解（图是盗的）如下：3、对索引表进行二分查找或者折半查找，得到要查找的数在哪一个块，然后进入对应的块里边顺序查找即可。 复杂度分析 时间复杂度：O(log(m)+N/m) 对比二分查找和折半查找

java代码：

/** * @param index 索引表 * @param obj 查找表 * @param key 要查找的数 * @param 每一块的长度，假设相等 blocklen * @return */ public static int blockSearch(int[] index, int[] obj, int key, int blocklen) { // 1.在index[ ] 中折半查找，确定要查找的key属于哪个块中 int i = binarySearch(index, key); //查找索引表获取数据在哪一块 if (i >= 0) { int j = i* blocklen; //块的起始索引 int len = (i + 1) * blocklen; //结束索引 // 在确定的块中用顺序查找方法查找key for (; j < len; j++) { if (key == st[j]) { System.out.println("查询成功"); return j; } } } System.out.println("查找失败"); return -1; }

参考博客