分块查找要求是顺序表,分块查找又称索引顺序查找,它是顺序查找的一种改进方法。 将n个数据元素"按块有序"划分为m块(m ≤ n)。 每一块中的结点不必有序,但块与块之间必须"按块有序"; 即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字; 而第2块中任一元素又都必须小于第3块中的任一元素,…… 1、先选取各块中的最大关键字构成一个索引表; 2、查找分两个部分:先对索引表进行二分查找或顺序查找,以确定待查记录在哪一块中; 3、在已确定的块中用顺序法进行查找。 示例: namespace IndexSear…

2020年8月28日 0条评论 0点热度 阅读全文

二叉排序树或者是一棵空树,或者是具有下列性质的二叉树: 若左子树不空,则左子树上所有结点的值均小于或等于它的根结点的值; 若右子树不空,则右子树上所有结点的值均大于或等于它的根结点的值; 左、右子树也分别为二叉排序树。 二叉树查找需要先生成一个二叉排序树,再遍历所有节点逐一比较其值与关键字是否相同,相同则返回;若一直找不到,则返回-1。 示例: public class BSTNode { public int Key { get; set; } public int Index { get; set; } pub…

2020年8月28日 0条评论 0点热度 阅读全文

斐波那契查找是区间中单峰函数的搜索技术,它在二分查找的基础上根据斐波那契数列进行分割的。在斐波那契数列找一个等于或略大于查找表中元素个数的数F[n],如果原查找表长度不足F[n],则补充重复最后一个元素,直到满足F[n]个元素时为止。完成后进行斐波那契分割,即F[n]个元素分割为前半部分F[n-1]个元素,后半部分F[n-2]个元素,根据值的关系确定往前或往后查找,直到找到时为止。如果一直找不到,则返回-1。 示例: public class Program { public static void Main(st…

2020年8月28日 0条评论 0点热度 阅读全文

插值查找是二分查找的更高效版本,它不会每次按2平分原问题规模,而是应用一个技巧来尽快的接近目标关键字。 示例 public class Program { public static void Main(string[] args) { int[] array = { 8, 11, 21, 28, 32, 43, 48, 56, 69, 72, 80, 94 }; Console.WriteLine(InterpolationSearch(array, 80, 0, array.Length - 1)); Cons…

2020年8月28日 0条评论 0点热度 阅读全文

二分查找也称折半查找,它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。 首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。 示例 public class Program { public sta…

2020年8月28日 0条评论 0点热度 阅读全文

顺序查找也称线性搜索(Linear Search),是在一个已知无(或有序)序队列中找出与给定关键字相同的值的具体位置。原理是让关键字与队列中的第1个(或最后1个)位置的值逐个比较,直到找出与给定关键字相同的值为止,它的缺点是效率低下。 示例 public class Program { public static void Main(string[] args) { int[] array = { 43, 69, 11, 72, 28, 21, 56, 80, 48, 94, 32, 8 }; Console.W…

2020年8月28日 0条评论 0点热度 阅读全文