便宜网站建设多少钱,大姚县建设工程招标网站,企业网站托管代运营,优化设计六年级上册答案顺序查找#xff1a;
对于无序的情况#xff1a;
什么是顺序查找#xff1a;顺序查找的实现方式#xff08;存储#xff09;#xff0c;是含有两种的方式进行存储的#xff0c;一种是顺序表的形式进行存储#xff0c;还有一种是使用链表的形式进行存储的。采用顺序查…顺序查找
对于无序的情况
什么是顺序查找顺序查找的实现方式存储是含有两种的方式进行存储的一种是顺序表的形式进行存储还有一种是使用链表的形式进行存储的。采用顺序查找的方式是含有也是含有两种查找方式的一个是从从头到尾进行查找一种是从尾到头进行查找的两种的效率都是差不多的时间复杂度基本上是一致的。
两种代码实现的方式
从头到尾
//从头到尾的方式进行代码的查找实现
public static void sortHead(int [] arr , int key){int i;//左边的for (i 0; i arr.length ; i){if(arr[i] key) {break;}};System.out.println(i);
}
直接进行时间复杂度的计算的判断
查找成功的时间复杂度为
查找成功
$$ Pi*(n - i 1)求和 $$ 查找失败
$$ n1 $$ 从尾到头来进行查找操作
//从尾的情况来进行相应的查找的操作
public static void tailSort(int [] arr , int key){int j;for (j arr.length - 1; j 0 ; j--) {if(arr[j] key){break;}}System.out.println(j);
}
比较一下两者的查找效率总体上来看得话这两个的效率数量级是一致的。
这种的查找的时间效率非常的低在数组的长度非常大的情况要进行对整个数组进行遍历操作耗时的这种是最简单的没有对数组当中的元素含有任何的限制的毫无顺序可言。但是对于单链表的形式进行存储的话就只能使用这种方式一个一个进行的遍历操作。
对于有序的情况
给定一个有序的数组当想要对这个数组当中的元素进行查找情况(由小到大的顺序进行存储的)。
当查找的元素arr[i] 的位置的元素大小小于key的值但是arr[i1]的位置大小是大于key的值的。这说明整个这个数组当中都没有一个等于key的元素的可以直接进行退出遍历操作了。 对于这种的有序的数组进行查找含有n1个不符合查找的情况的区间。当key的值落到了这个区间的话就可以直接进行退出循环遍历操作了。
public static void getSort(int [] arr , int key){Arrays.sort(arr);int i;for( i 0 ; i arr.length; i){if(arr[i] key){System.out.println(i);break;}//数组越界i1else if(i arr.length - 1 arr[i] key arr[i 1] key){System.out.println(找不到一个合适的);break;}}if(i arr.length){System.out.println(找不到元素);}
}
上面是采用的是顺序查找的方式进行实现的。
有没有更好的方式来将代码进行更加妙实现的呢
折半查找
对一个有序的数组可以进行有序的查找操作具体的实现流程是怎么样的
给定一个数组有序的使用两个指针的[low , high],分别指向第一个位置的元素和最后一个位置的元素。然后不断的取这两个位置的中间值(mid)根据中间值的位置来进行判断操作[是将high移动(mid - 1)还是将low移动(mid 1)].
以流程图的形式来将其进行展示 代码实现
package search;/*** program: 数据结构* description 二分查找* 二分查找是对有序的一串数组进行查找一个给定的数若查找不到的话就返回一个查找不到的信息。* author: YangTao* create: 2023-07-28 10:34**/
public class BinarySearch {public static void main(String[] args) {int [] arr new int[10];arr[0] 1;for (int i 1; i arr.length; i) {arr[i] arr[i - 1] * 2;}for (int i 0; i arr.length; i) {System.out.println(arr[i]);}
// 进行数据查找int number 16;int left 0;int right arr.length - 1;int middle 0;int index -1;while(left right){middle (left right)/2;if(arr[middle] number){index middle;break;}if(arr[middle] number){left;}if(arr[middle] number){right--;}}System.out.println(查找数得索引为 index);}
}
得到的节点连接的情况判定树 这样的判定树可以清晰的展示结果处于哪一层就得要进行比较多少次
得到的情况就是
查找成功----
$$ 12*23*44*4/ 11 $$ 查找失败----
$$ 4 * 4 8 * 5/ 12 $$ 通过公式将整个的时间复杂度都求出来的情况
查找成功的情况
$$ 1/n[1 2 * 2 3 * 4 4 * 8 h * 2^(h - 1)] $$ $$ ((1 n)/n) * log2(n 1) - 1 $$ $$ log2(n 1) - 1 $$ 在处理mid的时候会出现两种情况当使用的是向下取整的情况在比较左右子树的大小的情况左子树节点的个数可能是等于右子树的节点个数或者是为右子树节点个数减去1的情况。 但使用的是向上取整就会出现相反的情况
右子树节点的个数可能是等于左子树的节点个数或者是为左子树节点个数减去1的情况。
这种查找的形式的二叉树二会是一个平衡二叉树。左右子树的高度差的不会超过1。 分块查找 为数组建立一个索引表并将数组分割成为若干个块索引表中一次存放每个块内的最大值和块内元素的存储区间块内无序块间有序)
分块查找的过程 在索引表中确定key所属的分块索引表可以采用顺序查找也可以采用折半查找 在块内查找非有序只能顺序查找
3.2.分块查找手算过程
3.2.1.顺序查找索引表
以查找36为例 在索引表中依次遍历找到第一个大于它的值即40 移动到40指向的数组区间的第一个元素即数组下标9 从数组下标9开始遍历40→36 找到36
以查找17为例 在索引表中依次遍历找到第一个大于它的值即20 移动到20指向的数组区间的第一个元素即数组下标2 从数组下标2开始遍历13→19→16→20 此时移动到20数组下标为5到索引表中17的最后一个元素仍匹配失败说明表中没有17
3.2.2.折半查找索引表
索引表只是保存元素的数组区间方便在数组中寻找元素相对位置就算在索引表上找到相应元素还是得再去数组中重新再找一次
以查找30为例 low指向10high指向50mid (low high) / 2 指向 2即指向30 到30所指向的数组区间依次查找
以查找19为例 low指向10high指向50→mid指向30mid key high mid - 1 low指向10high指向20→mid指向10mid key low mid 1 low指向20high指向20→mid指向20mid key high mid - 1 low指向20high指向10→low high 折半查找结束 到low所指向的元素区间进行逐一遍历查找
去low指向区间查找的原因最后low的左边一定小于key而分块查找的索引表存放的是每块的最大值
除了能在key能在索引表上直接找到否则都要执行到low high才能确定key元素所可能存在的数组区间范围
代码实现分块查找 找到每一个块当中的最大的元素同时记录每一个块的起始位置和结束位置。
package search;import java.util.Scanner;/*** program: 数据结构* description* author: YangTao* create: 2024-04-23 16:54**/
public class BlockSearch {public static void main(String[] args) {int [] arr {9 , 22 , 12 , 14 , 35 , 42 , 44 , 38 , 48 , 60 , 58 , 47 , 78 , 80 , 77 , 82};//block的key的大小是属于逐渐递增的Block [] blocks {new Block(22 , 0 , 3) , new Block(44 , 4 , 7) , new Block(60 , 8 , 11) , new Block(82 , 12 , 15)};System.out.println(输入查找的元素);Scanner scanner new Scanner(System.in);int key scanner.nextInt();//进行查找int index search(blocks, arr, key);if(index -1){System.out.println(没有找到);}elseSystem.out.println(key位于的位置是 index);}public static int search(Block [] blocks , int [] arr , int key ){//对blocks的数组进行二分查找//当找到的元素是为key的话就可以直接获得这个位置的block的起始位置和结束位置。int low 0;int high blocks.length - 1;int mid -1;int indexBlock -1;while(low high){mid (low high) / 2;//找到了if(blocks[mid].key key){//进行返回indexBlock mid;break;}else if(blocks[mid].key key){high mid - 1;}else {low mid 1;}}//没有在主的索引位置找到相应的key值if(indexBlock -1){indexBlock low;}int index -1;//在分块当中继续进行查找操作for(int i blocks[indexBlock].low ; i blocks[indexBlock].high ; i){if(arr[i] key){index i;break;}}return index;}
}//定义一个存储索引块表的类
class Block{int key; //最大的节点的元素在块当中int low;int high;public Block(int key, int low, int high) {this.key key;this.low low;this.high high;}
}
