logo图片
数据结构与算法

搜索

在数据结构中搜索是指在一组项目中找到所需元素的过程。所需的元素称为"目标"。要搜索的项目集可以是任何数据结构,如列表、数组、链表、树或图。
搜索是指在项目集合中定位具有指定属性的所需元素。我们将使用以下常用且简单的搜索算法开始讨论。
技术与说明
线性搜索
线性搜索搜索所有项目,其最差执行时间为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"开头的名称的内存空间。

二分查找中的定位

在二分查找中,如果未找到所需的数据,则列表的其余部分分为上下两部分。在其中任何一个中进行搜索。
BST 第一步 BST 第二步 BST 第三步 BST 第四步
即使对数据进行了排序,二分查找也无法探测所需数据的位置。

插值搜索中的位置探测

插值搜索通过计算探针位置来查找特定项目。最初,探测位置是集合中最中间的项目的位置。
插值步骤一 插值第二步
如果发生匹配,则返回项目的索引。要将列表分成两部分,我们使用以下方法-
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
昵称: 邮箱:
Copyright © 2020 立地货 All Rights Reserved.
备案号:京ICP备14037608号-4