费氏搜索(Fibonacci Search)算法,运用费氏数列的搜索算法
费氏搜索(Fibonacci Search)算法有点像是二元搜索(Binary Search)算法,同样是在一个已排序好的数组中搜索元素,但是它在移动数组索引值时是去参考费氏数列(Fibonacci Sequence),而不是像二元搜索法那样总是去取索引的中间值。也由于费氏搜索法在移动数组索引值时只需要进行加减运算,不需乘、除法,因此它适合被用在不擅长处理乘、除法的 CPU 上。
MagicLen · https://magiclen.org
本站也提供繁體中文版。切換到繁體中文版
标签
在数据中找出目标的各种搜索算法,涵盖线性、二元、插补、指数与费氏搜索,图形节点的深度和广度优先走访,以及字符串比对与第 K 小元素的选取,并附上程序实作。
共 10 篇文章
费氏搜索(Fibonacci Search)算法有点像是二元搜索(Binary Search)算法,同样是在一个已排序好的数组中搜索元素,但是它在移动数组索引值时是去参考费氏数列(Fibonacci Sequence),而不是像二元搜索法那样总是去取索引的中间值。也由于费氏搜索法在移动数组索引值时只需要进行加减运算,不需乘、除法,因此它适合被用在不擅长处理乘、除法的 CPU 上。
图(graph)是由节点(node)和边(edge)组合而成的非线性结构,如果我们想要从其中的一个节点开始,走访到其有直接或是间接连接的其它所有节点,可以依靠深度优先搜索法(DFS, Depth-first Search)或是广度优先搜索法(BFS, Breadth-first Search)来达成。
这里所称的搜索(Search),是指在一个已排序好或是尚未排序好的集合中,将指定元素的键值(key)或是索引值(index)搜索出来,或者是给定某个条件,在集合中搜索出符合该条件的数据。在集合内搜索元素的方法当然不会只有一种,而不同方法搜索数据的难易度、速度和其它特性自然也会有所不同。搜索算法(Search Algorithm)就是搜索数据的方法,目前已知的方法有很多,在这篇文章中将会整理本站所介...
暴力字符串搜索(Brute-force Substring Search)算法是最基本的字符串搜索算法。它可以按照原文中字符的顺序,逐一与搜索样本(pattern)进行比对,判断目前的搜索位置是否就是搜索样本存在的位置。
插补搜索(Interpolation Search)算法又称为内插搜索算法,是二元搜索(Binary Search)算法的变体。这套算法可以在已排序好的串行中根据数据的预测线或近似线来进行高效率的搜索,近似线愈精准,搜索的效率就愈高。
指数搜索(Exponential Search)算法又称为双倍搜索(Doubling Search)算法或是蔓延搜索(Galloping Search)算法,是二元搜索(Binary Search)算法的变体。这套算法可以在已排序好的串行中进行高效率的搜索,要搜索的元素在串行中愈前面的话,搜索性能愈好。
二元搜索(Binary Search)算法又称为二分搜索(Half-Interval Search)算法或是对数搜索(Logarithmic Search)算法,顾名思义,这套算法的核心思想就在于「二分」,可以在已排序好的串行中进行高效率的搜索。
线性搜索(Linear Search)算法又称为循序搜索(Sequential Search)算法,是学习编程语言最先需要学会的搜索算法。它可以按照元素在数据结构中的顺序,从头开始进行走访,并连续判断目前走访到的元素是否是我们想要找的元素。
快速选择(Quickselect)算法是利用快速排序(Quick Sort)算法,在排序串行的同时,选择出串行中第 K 小或是第 K 大的元素。若我们只想要从串行中找出一个第 K 小或是第 K 大元素,使用快速选择法会比使用快速排序法来得快很多,因为前者不需要把串行的排序完整做完,平均只需线性时间即可找到结果。
Boyer-Moore-MagicLen 是笔者结合 Boyer-Moore-Horspool 和 Quick Search Algorithm 得出的字符串搜索算法。这篇文章会从 Boyer-Moore 算法讲起,再说明 Boyer-Moore-MagicLen 的概念、过程、程序实作与复杂度。