查找算法总结

您所在的位置：网站首页 › 排序算法的实验总结报告 › 查找算法总结

查找算法总结

2024-07-16 20:25| 来源: 网络整理| 查看: 265

查找算法详解

定义：根据给定的某一个值，在查找表中确定一个关键字等于给定的值的数据元素

查找算法的分类：动态查找和静态查找；无序查找和有序查找；无序查找和有序查找

平均查找的长度：ASL:需要和指定的key进行比较的关键字的个数的期望值。对于n个数据元素的查找表，查找成功的平均查找长度位：ASL = PI*CI 。PI时查找到第i个数据元素的概率。CI：找到第i个元素时已经比较过得出次数

顺序查找算法思想

从线性表的一端开始，顺序查找，直到找到指定的代码为止

代码实现 for(int i = 0 ; i < listlength ;i++ ){ if(list[i] == key)return i; }

进行优化

//在头部插入哨兵，依次从后往前进行比较，可以免去每一步都要检查是不是越界 list[0].key = key; //设置哨兵 for(int i = listlength ; list[i].key != key ; i--) return i; 算法分析

平均查找长度 ASL = (N+1)/2;

查找不成功时需要n+1次比较所以，时间复杂度时O(n)

分块查找基本思想

分块查找（Blocking Search）又称索引顺序查找，这是一种性能介于顺序查找和折半查找之间的一种查找方法。

分块查找中，需要建立一个“索引表”来划分块区域，通过定位某一块区域来查找相应信息；索引表包括两项内容：最大关键项、最大关键项块区域的指针项；对索引表来说是有序的顺序表，可用顺序查找和折半查找两种方法查找索引表；而对索引表所标识的块区域中的数据是无序的，所以只能使用顺序查找。

代码实现 int low = L; int high = R; int mid = (low+high)/2; while(low < high) //先折半查找索引表 { if(key == I[mid].maxkey) break; else { if(key < I[mid].maxkey) //缩小查找范围到左子序列 high = mid; else //缩小查找范围到右子序列 low = mid +1; } mid = (low+high)/2; } int i, end, start = I[mid].address; //找key值所在的区间首地址 if(mid == R) //确定查找的结束地址 end = len + 1; else end = I[mid+1].address; for(i = start; i < end; i++)//再顺序查找该区间 if(key == K[i].key) return i; //返回位置 return 0; } 算法分析

O(log2n)~O(n)之间

二分查找基本思想

首先元素时有序的，如果你要时没有顺序，那么对不起，先进行排序

二分查找又叫折半查找，就是把给定的值key和中间的节点进行比较，然后把线性表分成了两个子表，然后不断的进行继续分。

代码 //递归版本的代码 int search1(int a[],int key,int left,int right) { int mid = (left + right)/2; if(left > right)return -1; if(a[mid] == key)return mid; if(a[mid] < key)return search1(a[],key,mid+1,right); if(a[mid] > key)return search1(a[],key,left,mid-1); } //非递归版本的代码 int search2(int a[],int key,int length) { int left,right,mid; left = 0;right = length - 1; while(left key)right = mid -1; if(a[mid] < key)left = mid + 1; } } 算法分析

折半查找的运行过程可以使用二叉树来进行表示，这一棵树通常被称为“判定树”

对于具有n个节点的判定树，他的层次至多为 l o g 2 n log_2n log2n + 1 结果如果不是整数向下取整

ASL= l o g 2 ( n + 1 ) log_2(n+1) log2(n+1) - 1

最坏的情况下关键此比较的次数是 l o g 2 ( n + 1 ) log_2(n+1) log2(n+1) 所以时间复杂度树O( l o g 2 n log_2n log2n)

插值查找算法思想

基于二分查找算法，将查找点的选择改为自适应选择，可以提高查找效率，由于是二分查找的变异，所以插值查找属于有序查找

你仔细想一想，有必要一定选择二分查找吗？不一定把，你可以选择四分之一处吧，也可以选着三分之一处吧。所以说，折半查找不具有自适应性，这也就意味着有可能会有比他效率更搞的折半。

二分查找的计算

mid = (left + right) / 2 ，也就是 mid = low + 1/2 * （left - right）

我们改进一下

mid = left + (key - a[left]) /(a[right] - a[left]) * (right - left)

我们仅仅进行了系数1/2的改变，我们把1/2改进成了自适应的参数，这样跟关键字在有序表中的位置，让mid的值的变化更加接近关键字，这样也就简介减少了比较的次数

有一说一：当你表长大，而且关键字分布比较均匀的查找表来说，确实很好用，到那时如果分布很少不均匀，使用插值并不是一个好选择

代码 int left = 0 ,mid ,right = listlength -1; while(left list[mid]) { left = mid + 1; } else { return mid; } } 算法分析

查找成功或者失败的时间复杂度O( l o g 2 ( l o g 2 n ) log_2(log_2n) log2(log2n))

斐波那契查找基本思想

还是二分查找的一种提升算法，通过利用黄金比例在数列中选择查找点进行查找，来提高查找效率。那么这也是一种有序查找算法

要求开始表中记录的个数为某个斐波那契数小1，及n = F(k) - 1;

开始将key值和第F(k-1)位置的记录进行比较（也就是：mid = left + F（k-1）- 1）比较结果也分为三种

1：相等，那么return mid

2; key > mid , left = mid + 1,k-=2;

解释：low = mid + 1 上面查找的元素在【mid + 1 ，right 】范围内，k-=2说明分为在[mid+1 ， right]内的个数为n - (F(k-1)) =

F(k) - 1 - F(k-1) = F(k) - F(k-1)-1 = F(k-2) -1 个，所以可以使用递归应用斐波那契查找

3 key < mid , right = mid - 1 , k-=1;

解释： low = mid + 1 说明待查找的元素在[left, mid -1]内， k-= 1 说明非为[left , mid-1]内的元素个数为F(k-1) - 1个，所以可以递归的应用斐波那契数列

代码 void fib(int *f) { f[0],f[1] = 1; for(int i = 2; i < 20; i++)//20仅仅是一个暂定的数字可以修改 { f[i] f[i-2] + f[i - 1]; } } int fibsearch(int *a, int key, int length) { int i,left = 0,right = length - 1; int mid = 0; int k = 0; int F[20];//20仅仅是一个暂定的数字可以修改 fib(F); while(n > F[k] - 1)//计算处n在斐波那契中的数列 k++; for(i = length ; i < F[k - 1] ;i++) a[i] = a[right];//补全数组 while(left key){ right = mid - 1; k = k -1; } else if(a[mid] < key ) { left = mid = 1; k-= 2; } else { if(mid data == key)return root; else if(root->data > key)root = root->lchild; else root = root->rchild; } 算法分析

在正常的情况下，应该是O( l o g 2 n log_2n log2n)，但是要是极端一点O(n)也是有可能的。所以需要优化，下面给出优化算法

平衡查找树之2-3查找树

2-3查找树定义：

2-节点：含有一个键和两条链接，左链接指向的2-3树中的键都小于该节点，右链接指向的2-3树中的键都大于该节点。

3-节点：含有两个键和三条链接，左链接指向的2-3树中的键都小于该节点，链接指向的2-3树中的键都位于该节点的两个键之间，右链接指向的2-3树中的键都大于该节点。

这样多了一个3节点之后，树就多了分配节点的能力

具体文章请参考

代码 public class Tree234 { private Node root = new Node() ; /*public Tree234(){ root = new Node(); }*/ //查找关键字值 public int find(long key){ Node curNode = root; int childNumber ; while(true){ if((childNumber = curNode.findItem(key))!=-1){ return childNumber; }else if(curNode.isLeaf()){//节点是叶节点 return -1; }else{ curNode = getNextChild(curNode,key); } } } public Node getNextChild(Node theNode,long theValue){ int j; int numItems = theNode.getNumItems(); for(j = 0 ; j return theNode.getChild(j); } } return theNode.getChild(j); } //插入数据项 public void insert(long dValue){ Node curNode = root; DataItem tempItem = new DataItem(dValue); while(true){ if(curNode.isFull()){//如果节点满数据项了，则分裂节点 split(curNode); curNode = curNode.getParent(); curNode = getNextChild(curNode, dValue); }else if(curNode.isLeaf()){//当前节点是叶节点 break; }else{ curNode = getNextChild(curNode, dValue); } }//end while curNode.insertItem(tempItem); } public void split(Node thisNode){ DataItem itemB,itemC; Node parent,child2,child3; int itemIndex; itemC = thisNode.removeItem(); itemB = thisNode.removeItem(); child2 = thisNode.disconnectChild(2); child3 = thisNode.disconnectChild(3); Node newRight = new Node(); if(thisNode == root){//如果当前节点是根节点，执行根分裂 root = new Node(); parent = root; root.connectChild(0, thisNode); }else{ parent = thisNode.getParent(); } //处理父节点 itemIndex = parent.insertItem(itemB); int n = parent.getNumItems(); for(int j = n-1; j > itemIndex ; j--){ Node temp = parent.disconnectChild(j); parent.connectChild(j+1, temp); } parent.connectChild(itemIndex+1, newRight); //处理新建的右节点 newRight.insertItem(itemC); newRight.connectChild(0, child2); newRight.connectChild(1, child3); } //打印树节点 public void displayTree(){ recDisplayTree(root,0,0); } private void recDisplayTree(Node thisNode,int level,int childNumber){ System.out.println("levle="+level+" child="+childNumber+" "); thisNode.displayNode(); int numItems = thisNode.getNumItems(); for(int j = 0; j recDisplayTree(nextNode, level+1, j); }else{ return; } } } //数据项 class DataItem{ public long dData; public DataItem(long dData){ this.dData = dData; } public void displayItem(){ System.out.println("/"+dData); } } //节点 class Node{ private static final int ORDER = 4; private int numItems;//表示该节点有多少个数据项 private Node parent;//父节点 private Node childArray[] = new Node[ORDER];//存储子节点的数组，最多有4个子节点 private DataItem itemArray[] = new DataItem[ORDER-1];//存放数据项的数组，一个节点最多有三个数据项 //连接子节点 public void connectChild(int childNum,Node child){ childArray[childNum] = child; if(child != null){ child.parent = this; } } //断开与子节点的连接，并返回该子节点 public Node disconnectChild(int childNum){ Node tempNode = childArray[childNum]; childArray[childNum] = null; return tempNode; } //得到节点的某个子节点 public Node getChild(int childNum){ return childArray[childNum]; } //得到父节点 public Node getParent(){ return parent; } //判断是否是叶节点 public boolean isLeaf(){ return (childArray[0] == null)?true:false; } //得到节点数据项的个数 public int getNumItems(){ return numItems; } //得到节点的某个数据项 public DataItem getItem(int index){ return itemArray[index]; } //判断节点的数据项是否满了（最多3个） public boolean isFull(){ return (numItems == ORDER-1) ? true:false; } //找到数据项在节点中的位置 public int findItem(long key){ for(int j = 0 ; j break; }else if(itemArray[j].dData == key){ return j; } } return -1; } //将数据项插入到节点 public int insertItem(DataItem newItem){ numItems++; long newKey = newItem.dData; for(int j = ORDER-2 ; j >= 0 ; j--){ if(itemArray[j] == null){//如果为空，继续向前循环 continue; }else{ long itsKey = itemArray[j].dData;//保存节点某个位置的数据项 if(newKey itemArray[j+1] = newItem;//如果比新插入的数据项小，则直接插入 return j+1; } } } //如果都为空，或者都比待插入的数据项大，则将待插入的数据项放在节点第一个位置 itemArray[0] = newItem; return 0; } //移除节点的数据项 public DataItem removeItem(){ DataItem temp = itemArray[numItems-1]; itemArray[numItems-1] = null; numItems--; return temp; } //打印节点的所有数据项 public void displayNode(){ for(int j = 0 ; j

【本文地址】

公司简介

联系我们