温故而知新

--------------------------------

讲解一基础理论

--------------------------------

讲解二代码学习

在Java编程中查找搜索是一项常见任务。

不同的查找算法在不同的数据结构和数据量下表现

本文将详细分析Java中常见的查找算法包括顺序查找、二分查找、插值查找、斐波那

契查找、哈希查找、二叉树查找、2-3树查找、红黑树查找、B树/B树查找等并探讨它们的适用

--------------------------------

讲解一基础理论

查找是在大量的信息中寻找一个特定的信息元素在计算机应用中查找是常用的基本运算

二、为什么需要查找

查找算法的目的就是要尽可能快的找到满足给定条件的元素设想有一种方法能让你直接拿到该

那么所谓的查找算法为什么有的快有的慢呢你可以这样去理解。

其实所有的查找算法都在

每一次查找操作其实都是在做排除如果说有一种方法能以O(1)的复杂度找到元素那么其实

说明它可以一下子排除候选集中的所有不相关元素当然这种算法还是最理想化的。

不同查找算法的优劣其实也就是看它能不能一次排除更多的元素比如暴力穷举法这种方式就是

一次只能排除一个元素显然是最慢的如果一次能排除一半的元素那么这就是二分如果每一

所以学习查找算法时要考虑这个算法一次能排除多少元素那么排除的越多就是越好的。

因为讲查找都是基于某一数据结构所以本篇文章介绍各个数据结构下的查找算法讲解每个算法

--------------------------------

讲解二代码学习

Search是一种基础的查找算法也被称为线性查找。

它是一种逐个遍历

数据集逐个比较目标值和数据集中元素的查找方法。

虽然它在大数据集下性能较差但在小规模

算法原理

顺序查找算法的原理非常简单从数据集的第一个元素开始逐个与目标值进行比较直到找到相

等的元素或遍历完整个数据集。

如果找到相等的元素返回该元素的位置如果遍历完整个数据集

都没有找到相等的元素返回一个特殊的标识如-1表示目标值不存在于数据集中。

算法步骤

Search是一种基本的搜索算法它按顺序逐个检查数组中的元素直到

public

它使用for循环遍历数组如果找到与目标值相等的元素则返回该元素的索引。

如果循环结束仍

未找到目标元素则返回

7。

根据查找的结果程序将输出目标元素在数组中的索引位置或者提示未找到目标元素。

适用场景

小规模数据集当数据集规模较小且不需要频繁查找时顺序查找是一种简单有效的选择。

数据集无序顺序查找不依赖数据的有序性可以在无序的数据集中进行查找操作。

知识小结

顺序查找虽然不是最高效的查找算法但它的简单性和直观性使得它在某些场景下非常有用。

二、二分查找

它适用于有序数组通过每次将待查找范围缩小一半快速定位目标元素的位置。

算法原理

二分查找的基本思想是将待查找区间的中间元素与目标元素进行比较如果相等则查找成功返回元

素下标

如果中间元素大于目标元素则在左半部分继续查找如果中间元素小于目标元素则在右半部分继续

算法步骤

初始化左指针left为数组第一个元素的下标右指针right为数组最后一个元素的下标。

步骤二查找中间元素

将中间元素与目标元素进行比较如果中间元素等于目标元素则查找成功返回mid。

如果中间元素大于目标元素则将right指针移到mid

步骤四重复查找

有序数组的查找二分查找适用于有序数组能够快速定位目标元素。

数据查询优化在大规模有序数据集中二分查找能够提高查找效率常用于数据库查询等场景。

知识小结

但需要注意的是二分查找只适用于有序数据。

在实际应用中根据数据特点选择合适的查找算法可以有效提

三、插值查找

Search是一种基于数学插值的查找算法它是二分查找的改进版本。

插值查找算法适用于均匀分布的有序数据集通过估算目标值的位置它能够更快速地定位到目标

算法原理

插值查找算法的核心思想是根据目标元素的预估位置来缩小查找范围。

假设我们要查找的数据集是有序的如果该数据集在数值上是均匀分布的那么插值查找会非常高

其中arr

如果估计值等于目标值查找成功返回估计位置。

如果估计值小于目标值在估计位置的右侧继续查找。

如果估计值大于目标值在估计位置的左侧继续查找。

步骤三

重复步骤一和步骤二直到找到目标元素或查找范围缩小到只包含一个元素。

Java代码实现

插值查找是一种查找算法用于在有序数组或列表中快速定位目标元素。

public

参数并返回目标元素在数组中的位置。

在每一步迭代中根据插值公式估算目标元素在数组中的

位置并将搜索范围缩小到该位置的左边或右边。

如果找到目标元素返回其位置如果未找到

请注意插值查找适用于均匀分布的数据。

在某些情况下插值查找可能不如二分查找准确。

在实

适用场景

在这些条件下插值查找算法的效率较高。

然而如果数据分布不均匀插值查找可能不如二分查

插值查找算法的时间复杂度为O(log(log(n)))它相较于普通二分查找在均匀分布的数据集中的查

四、斐波那契查找

斐波那契查找算法是一种基于分割思想的查找算法它通过将数组分割成按照斐波那契数列定义的

特殊比例来确定查找范围。

与二分查找类似斐波那契查找也是一种高效的有序数组查找算法

但其优势

斐波那契查找的基本思想是将数组按照斐波那契数列的比例分割成两部分

算法步骤如下

将待查找数组长度扩展至斐波那契数列的值并用原数组最后一个元素填充。

步骤三

若找到目标元素返回其索引若查找范围缩小至一个元素且不等于目标元素说明查找失败。

Java代码实现

generateFibonacci(arr.length);int

0;while

{System.out.println(目标元素在数组中的索引为

result);}

{System.out.println(目标元素不在数组中。

);}}

适用场景

斐波那契查找算法是一种高效的有序数组查找算法它的时间复杂度为O(log

然而在实际应用中由于其需要生成斐波那契数列并进行数组扩展可能会带来一定的额外开

知识小结

在选择查找算法时我们需要综合考虑数据规模、数据分布和性能要求等因素选择合适的算法来

五、哈希查找

Search利用哈希函数将关键字映射到数组的特定位置即哈希表。

通过直接访

问哈希表的索引可以快速定位目标元素。

哈希函数负责将关键字映射到哈希表中的特定位置这

算法步骤

初始化哈希表创建一个具有足够容量的哈希表通常使用数组实现。

插入元素

将关键字经过哈希函数计算得到索引然后将元素插入到对应索引的桶中。

查找元素

将待查找的关键字经过哈希函数计算得到索引然后在对应索引的桶中查找目标元素。

Java代码实现

哈希查找算法是通过哈希函数将关键字映射到哈希表的某个位置以加快查找速度。

import

hash(key);table[index].add(key);}//

查找操作public

hash(key);table[index].remove(key);}

}public

插入数据hashTable.insert(apple);hashTable.insert(banana);hashTable.insert(cherry);//

apple:

删除数据hashTable.delete(apple);System.out.println(Search

apple

函数将字符串映射到哈希表的索引。

请注意这只是一个简单的哈希查找算

适用场景

在散列冲突多个关键字映射到同一个索引位置较少的情况下哈希查找具有很好的性能。

知识小结

哈希查找算法通过哈希函数将关键字映射到数组索引实现了快速的查找操作。

然而需要注意处

理散列冲突的情况常见的方法包括开放地址法和链地址法。

选择合适的哈希函数和处理冲突的方

六、二叉树查找

二叉树查找是一种常见的数据结构和算法用于在有序数据集中高效地查找目标元素。

算法原理

二叉树查找算法基于二叉树数据结构其中每个节点最多有两个子节点左子节点和右子节点。

算

法利用二叉树的有序性质从根节点开始比较目标元素与当前节点的值根据比较结果决定向左子

算法步骤

比较目标元素与当前节点的值。

如果目标元素等于当前节点的值查找成功返回当前节点。

如果目标元素小于当前节点的值转到左子树如果大于转到右子树。

步骤3:

BinarySearchTree();tree.insert(5);tree.insert(3);tree.insert(7);tree.insert(2);tree.insert(4);System.out.println(tree.search(4));

输出:

trueSystem.out.println(tree.search(6));

输出:

二叉树查找算法是一种高效的查找方法通过利用二叉树的有序性可以快速查找目标元素。

它适

用于静态数据集但对于动态数据集可能需要其他更复杂的数据结构如红黑树或B树。

了解二叉树查

找算法有助于优化程序的查找性能。

在实际编程中可以使用递归或迭代方式实现二叉树查找根

七、2-3树查找

2-3树是一种自平衡查找树它的每个节点可以包含2个或3个子节点同时满足以下性质

所有叶子节点在同一层级。

每个节点要么是2-节点含有一个元素要么是3-节点含有两个元素。

2-节点的两个子节点分别比父节点的元素小和大。

3-节点的三个子节点分别比父节点的两个元素小、中和大。

2-3树的插入和删除操作会使树保持平衡确保树的高度最小从而提供高效的查找、插入和删除性能。

算法步骤

在2-3树中查找插入位置如果为2-节点直接插入如果为3-节点分裂成两个2-节点向上递归。

如果向上递归导致父节点为3-节点继续分裂直到树的根节点。

删除操作

在2-3树中找到要删除的节点删除操作分情况讨论。

删除节点后根据需要进行节点的合并和分裂确保树的平衡性。

Java代码实现

searchKey(node.children[node.numKeys],

key);}public

TreeNode(newNode.keys[0]);newRoot.children[0]

newNode.children[0];newRoot.children[2]

newRoot;root.isLeaf

node.children[i];node.children[i]

child.children[0];node.children[i

node.numKeys

child.children[1];node.children[i]

node.numKeys

);}System.out.println(node.keys[i]);}printTree(node.children[node.numKeys],

level

TwoThreeTree();tree.insert(10);tree.insert(20);tree.insert(5);tree.insert(6);tree.insert(12);tree.insert(30);tree.insert(7);System.out.println(2-3树的结构);tree.printTree();System.out.println(查找结果);System.out.println(查找5

tree.search(5));System.out.println(查找15

tree.search(15));}

这段代码演示了一个简单的2-3树的实现包括插入和查找操作。

你可以根据需要扩展它。

在这个

例子中TreeNode类表示2-3树的节点。

TwoThreeTree

希望这能帮到你

当需要高效的查找、插入和删除操作时特别是在动态数据集上。

当数据集需要频繁地进行修改操作时2-3树的自平衡性能保证了树的高度较小提供了快速的操作性能。

知识小结

2-3树是一种自平衡查找树通过节点的合并和分裂保持树的平衡性提供了高效的查找、插入

和删除操作。

在动态数据集和需要频繁修改操作的情况下2-3树是一个优秀的选择。

八、红黑树查找

红黑树是一种自平衡的二叉查找树它在每个节点上都增加了一个额外的属性表示节点的颜色可

每个节点要么是红色要么是黑色。

根节点是黑色。

每个叶子节点NIL节点空节点是黑色。

如果一个节点是红色其子节点必须是黑色。

从任意节点到其每个叶子的所有路径都包含相同数目的黑色节点这被称为黑高度相同。

这些性质保证了红黑树的平衡性最长的路径不超过最短路径的两倍保证了在增删查改等操作时

算法步骤

当插入一个节点时首先按照二叉查找树的规则找到其应该插入的位置然后将节点

删除操作

删除一个节点时首先按照二叉查找树的规则找到替代节点。

如果被删除的节点或替

代节点是红色可以直接删除。

如果被删除的节点是黑色则可能破坏了红黑树的性质需要通过

Java代码实现

Tree是一种自平衡二叉搜索树它在插入和删除操作时通过颜色变换和旋转

class

k.parent;rightRotate(k);}k.parent.color

1;leftRotate(k.parent.parent);}}

else

k.parent;leftRotate(k);}k.parent.color

1;rightRotate(k.parent.parent);

}}if

在这个示例中我们实现了红黑树的基本操作包括节点插入insert、修复插入导致的红黑树

不平衡fixInsert、左旋leftRotate、右旋rightRotate以及查找节点searchTree。

请注意这只是一个简单的示例实际的红黑树实现可能会更加复杂具体实现可能会

适用场景

需要频繁插入和删除操作的大型数据集红黑树在维持平衡性的同时插入和删除的性能相对较好。

需要快速查找、插入和删除的数据库索引

数据库中的索引通常使用红黑树来维持数据的有序性和高效的增删查改操作。

知识小结

红黑树是一种自平衡的二叉查找树通过巧妙的旋转和颜色变换保持了树的平衡性。

它在大型数据集的插入、删除和查找操作中表现出色。

但需要注意的是红黑树的实现较为复杂

九、B树/B树查找

在Java编程中B树和B树是常用的自平衡查找树结构用于高效地存储和检索大量数据。

本文将深入探讨B树和B树的算法原理、步骤、Java代码实现、适用场景以及总结它们的重要特

算法原理

B树是一种多路搜索树每个节点可以包含多个子节点。

每个节点有多个关键字关键字按照升序排列。

B树的高度是平衡的使得查找、插入和删除操作都可以在O(log

B树也是一种多路搜索树与B树不同的是B树的所有关键字都在叶子节点上。

叶子节点通过指针相互连接形成有序链表提高范围查询的性能。

B树的高度也是平衡的查找、插入和删除操作的性能稳定。

算法步骤

从根节点开始按照关键字的大小进行比较确定子节点的位置。

递归地进入子节点直到找到目标关键字或达到叶子节点。

执行插入、删除或查找操作。

从根节点开始按照关键字的大小进行比较确定子节点的位置。

递归地进入子节点直到找到目标关键字或达到叶子节点。

执行插入、删除或查找操作。

Java代码实现

B树B-Tree是一种自平衡的树数据结构通常用于数据库和文件系统中进行范围查询。

class

{i;}}insertNonFull(x.childNodes[i],

key);}}private

创建一个度为3的B树bTree.insert(3);bTree.insert(8);bTree.insert(12);bTree.insert(15);bTree.insert(20);bTree.insert(25);bTree.insert(27);System.out.println(bTree.search(15));

trueSystem.out.println(bTree.search(30));

false}

请注意B树的性能和效率与其度数degree有关你可以根据实际需求调整度数以获得更好的

请注意这只是一个基本的示例实际应用中可能需要更多的功能和错误处理。

import

{i;}insert(node.children.get(i),

value);}}

BPlusTree();tree.insert(5);tree.insert(8);tree.insert(3);System.out.println(tree.search(5));

输出trueSystem.out.println(tree.search(4));

输出false}

请注意这只是B树查找算法的基本实现。

在实际应用中可能需要添加删除、更新等功能并

在真实的场景中推荐使用现有的B树实现例如Java中的TreeMap。

适用场景

B树和B树适用于需要高效地管理大量数据的场景例如数据库管理系统、文件系统和搜索引擎索

数据量大当数据量较大时B树和B树的平衡性确保了高效的查找性能。

范围查询B树的叶子节点形成有序链表适合范围查询操作。

高度平衡B树和B树的高度保持平衡保证了操作的一致性性能。

知识小结

B树和B树是高效的查找算法用于管理大规模数据。

它们具有平衡性、高效性和适应性等优点

适用于各种数据存储和检索需求。

选择B树或B树取决于具体应用场景和性能需求。

十、知识小结

有序数组当然是有序了不过它有一个特点就是它的每一个元素相当于把整个候选集分成了两

方法一二分查找

这个大家比较熟悉了每次可以排除一半时间复杂度是O(log2N)

方法二插值查找

这个数组也是有序的但有一个特点每个元素相差一样说明它们之间是均匀分布的那么让你

来查找一个75你会怎么办

现在闭眼想象一下元素都是均匀分布的所以你知道50肯定在中间90肯定接近末尾20

肯定离开头比较近。

那么我们可以每次查找时找到最接近的那个数字而它的位置大概就在

所以我们每次比较的位置就是通过以上公式来计算的这样每次就不像2分查找那样傻傻的

适用情况均匀分布

其实也是一种划分数组进行排除的方式据说性能优于二分查找但好像看不懂证明所以知

这节介绍数下的查找方法树的排除和数组的排除类似数组是排除一部分树更形象一点排除一个分支。

无序树不限于二叉树

其实就是有两种结点2node和3node和二叉树长的大差不差。

查找方式也几乎雷同只是构建

红黑树

红黑树就是树2-3树变成了二叉树2-3树中的3结点变成红色链接

再谈二叉查找树2-3树红黑树

以上说了二叉查找树2-3树红黑树整了这么多最好也是O(log2N)的效率而且2-3红

黑似乎还要比二叉查找树复杂啊

其实2-3树红黑树都有一个目的就是要尽量接近平衡二叉树只有接近了平衡二叉树才能有

这里我们其实还忽略了另一个方面就是这个结构并不仅仅用来查找在实际项目中还要增加

随着增加删除的增多慢慢的变的不平衡了不平衡了查找效率就下来了而为了维持平衡

要付出巨大的插入删除代价这显然是不可接受的因为我们的实际业务不仅仅是要求查找效率

高而2-3树红黑树就在插入和删除时能尽量维持平衡这也就在插入删除查找之间找到

B树是2-3树的更一般化它也是一种平衡树结点也是有序的每个结点可以有多个值所以很

B树和B树类似关于B树B树的应用可以参考[数据库基础概念]中关于索引的讨论一文

散列表

我们知道元素是在计算机中存储的那么每个元素就有一个地址找到了这个地址想当于找到

其实无论是数组也好树也好我们拿一个元素来检查是不是要找的值实际上是先通过地址来得

那么说能不能直接定位到要查找元素的地址呢假如我们有一个函数可以根据元素的值来计

address

而散列表的思想就是来自于此。

以上函数就是散列表中最关键的hash函数。

散列表一般长这样

一般散列表的结构都是有一个数组链表来组成的。

理想情况下可以根据要查找的元素直接计

所以我们要根据自己的数据集的特点看查找增加删除更新这些操作在该数据集上的频率等

当然还要考虑到实际计算机中不同存储体系的性能差距如B树B树在数据库中的应用就体现了

顺序查找

不同的查找算法适用于不同的场景选择合适的查找算法可以有效提高程序的运行效率。