搜索基础教程文档
收录于 2023-04-20 00:10:05 · بالعربية · English · Español · हिंदीName · 日本語 · Русский язык · 中文繁體
在数据结构中搜索是指在一组项目中找到所需元素的过程。所需的元素称为"目标"。要搜索的项目集可以是任何数据结构,如列表、数组、链表、树或图。
搜索是指在项目集合中定位具有指定属性的所需元素。我们将使用以下常用且简单的搜索算法开始讨论。
技术与说明 |
线性搜索
线性搜索搜索所有项目,其最差执行时间为n,其中n是项目数。
|
二分搜索
二分搜索要求项目按排序顺序,但其最差执行时间是恒定的,并且比线性搜索快得多。
|
插值搜索
插值搜索要求项目按排序顺序,但其最差执行时间是 O(n),其中 n 是items,它比线性搜索快得多。
|
线性搜索
线性搜索是一种非常简单的搜索算法。在这种类型的搜索中,对所有项目逐一进行顺序搜索。检查每个项目,如果找到匹配项,则返回该特定项目,否则搜索将持续到数据收集结束。
算法
Linear Search ( Array A, Value x) Step 1: Set i to 1 Step 2: if i > n then go to step 7 Step 3: if A[i] = x then go to step 6 Step 4: Set i to i + 1 Step 5: Go to Step 2 Step 6: Print Element x Found at index i and go to step 8 Step 7: Print element not found Step 8: Exit
伪代码
procedure linear_search (list, value) for each item in the list if match item == value return the item's location end if end for end procedure
二分搜索
二分查找是一种快速查找算法,运行时间复杂度为Ο(log n)。这种搜索算法的工作原理是分而治之。为使该算法正常工作,数据集合应采用排序形式。
二分搜索通过比较集合中最中间的项目来查找特定项目。如果发生匹配,则返回项目的索引。如果中间项大于该项,则在中间项左侧的子数组中搜索该项。否则,在中间项右侧的子数组中搜索该项。这个过程也在子数组上继续进行,直到子数组的大小减小到零。
二分搜索如何工作?
为了使二分搜索起作用,必须对目标数组进行排序。我们将通过一个图示的例子来学习二分查找的过程。下面是我们的排序数组,假设我们需要使用二分搜索来搜索值 31 的位置。
首先,我们将使用这个公式确定数组的一半-
mid = low + (high-low) / 2
这里是 0 + (9-0 )/2 = 4(整数值 4.5)。所以,4 是数组的中点。
现在我们将存储在位置 4 的值与正在搜索的值进行比较,即 31、我们发现位置 4 的值是 27,这是不匹配的。由于值大于 27 并且我们有一个排序数组,所以我们也知道目标值必须在数组的上部。
我们将低值更改为中值 + 1 并再次找到新的中值。
low = mid + 1 mid = low + (high-low) / 2
我们的新中单现在是 7、我们将存储在位置 7 的值与目标值 31 进行比较。
存储在位置 7 的值不匹配,而不是我们正在寻找的值。因此,该值必须位于该位置的下部。
因此,我们再次计算中间值。这次是 5、
我们将存储在位置 5 的值与我们的目标值进行比较。我们发现它是匹配的。
我们得出结论,目标值 31 存储在位置 5、
二分搜索将可搜索项减半,从而将要进行的比较次数减少到非常少。
伪代码
二分查找算法的伪代码应该是这样的-
Procedure binary_search A ← sorted array n ← size of array x ← value to be searched Set lowerBound = 1 Set upperBound = n while x not found if upperBound < lowerBound EXIT: x does not exists. set midPoint = lowerBound + ( upperBound-lowerBound ) / 2 if A[midPoint] < x set lowerBound = midPoint + 1 if A[midPoint] > x set upperBound = midPoint -1 if A[midPoint] = x EXIT: x found at location midPoint end while end procedure
插值搜索
插值搜索是二分搜索的改进变体。此搜索算法适用于所需值的探测位置。为使该算法正常工作,数据收集应该是有序且均匀分布的。
与线性搜索相比,二分搜索在时间复杂度方面具有巨大优势。线性搜索的最坏情况复杂度为 Ο(n),而二分搜索的复杂度为 Ο(log n)。
在某些情况下,可能会提前知道目标数据的位置。例如,在电话簿的情况下,如果我们要搜索 Morphius 的电话号码。在这里,线性搜索甚至二分搜索都会显得很慢,因为我们可以直接跳转到存储以"M"开头的名称的内存空间。
二分查找中的定位
在二分查找中,如果未找到所需的数据,则列表的其余部分分为上下两部分。在其中任何一个中进行搜索。
即使对数据进行了排序,二分查找也无法探测所需数据的位置。
插值搜索中的位置探测
插值搜索通过计算探针位置来查找特定项目。最初,探测位置是集合中最中间的项目的位置。
如果发生匹配,则返回项目的索引。要将列表分成两部分,我们使用以下方法-
mid = Lo + ((Hi-Lo) / (A[Hi]-A[Lo])) * (X-A[Lo]) where − A = list Lo = Lowest index of the list Hi = Highest index of the list A[n] = Value stored at index n in the list
如果中间项大于该项,则在中间项右侧的子数组中再次计算探测位置。否则,在中间项左侧的子数组中搜索该项。这个过程也在子数组上继续进行,直到子数组的大小减小到零。
插值搜索算法的运行时间复杂度为
Ο(log (log n)),而BST在有利情况下的运行时间复杂度为
Ο(log n)。
算法
由于它是现有 BST 算法的即兴创作,我们提到了使用位置探测搜索"目标"数据值索引的步骤-
Step 1 − Start searching data from middle of the list. Step 2 − if it is a match, return the index of the item, and exit. Step 3 − if it is not a match, probe position. Step 4 − Divide the list using probing formula and find the new midle. Step 5 − if data is greater than middle, search in higher sub-list. Step 6 − if data is smaller than middle, search in lower sub-list. Step 7 − Repeat until match.
伪代码
A → Array list N → Size of A X → Target Value Procedure Interpolation_Search() Set Lo → 0 Set Mid →-1 Set Hi → N-1 while X does not match if Lo equals to Hi OR A[Lo] equals to A[Hi] EXIT: Failure, Target not found end if Set Mid = Lo + ((Hi-Lo) / (A[Hi]-A[Lo])) * (X-A[Lo]) if A[Mid] = X EXIT: Success, Target found at Mid else if A[Mid] < X Set Lo to Mid+1 else if A[Mid] > X Set Hi to Mid-1 end if end if End While End Procedure