8.线性搜索算法和二进制搜索算法

简介: 8.线性搜索算法和二进制搜索算法

算法:线性搜索算法

线性搜索是一种非常简单的搜索算法。在这种类型的搜索中,逐个对所有项目进行顺序搜索。检查每个项目,如果找到匹配项,则返回该特定项目,否则搜索将继续,直到数据收集结束。

算法

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
 end if
   end for
end procedure

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

算法:二进制搜索算法

二进制搜索是一种快速搜索算法,运行时复杂度为Ο(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


目录
相关文章
|
15天前
|
机器学习/深度学习 算法 安全
【无人机三维路径规划】基于非支配排序的鲸鱼优化算法NSWOA与多目标螳螂搜索算法MOMSA求解无人机三维路径规划研究(Matlab代码实现)
【无人机三维路径规划】基于非支配排序的鲸鱼优化算法NSWOA与多目标螳螂搜索算法MOMSA求解无人机三维路径规划研究(Matlab代码实现)
|
17天前
|
机器学习/深度学习 算法 安全
【无人机三维路径规划】多目标螳螂搜索算法MOMSA与非支配排序的鲸鱼优化算法NSWOA求解无人机三维路径规划研究(Matlab代码实现)
【无人机三维路径规划】多目标螳螂搜索算法MOMSA与非支配排序的鲸鱼优化算法NSWOA求解无人机三维路径规划研究(Matlab代码实现)
|
2月前
|
机器学习/深度学习 算法 文件存储
神经架构搜索NAS详解:三种核心算法原理与Python实战代码
神经架构搜索(NAS)正被广泛应用于大模型及语言/视觉模型设计,如LangVision-LoRA-NAS、Jet-Nemotron等。本文回顾NAS核心技术,解析其自动化设计原理,探讨强化学习、进化算法与梯度方法的应用与差异,揭示NAS在大模型时代的潜力与挑战。
300 6
神经架构搜索NAS详解:三种核心算法原理与Python实战代码
|
18天前
|
存储 算法 数据可视化
基于禁忌搜索算法的TSP问题最优路径搜索matlab仿真
本程序基于禁忌搜索算法解决旅行商问题(TSP),旨在寻找访问多个城市的最短路径。使用 MATLAB 2022A 编写,包含城市坐标生成、路径优化及结果可视化功能。通过禁忌列表、禁忌长度与藐视准则等机制,提升搜索效率与解的质量,适用于物流配送、路径规划等场景。
|
6月前
|
存储 算法 调度
基于和声搜索优化算法的机器工作调度matlab仿真,输出甘特图
本程序基于和声搜索优化算法(Harmony Search, HS),实现机器工作调度的MATLAB仿真,输出甘特图展示调度结果。算法通过模拟音乐家即兴演奏寻找最佳和声的过程,优化任务在不同机器上的执行顺序,以最小化完成时间和最大化资源利用率为目标。程序适用于MATLAB 2022A版本,运行后无水印。核心参数包括和声记忆大小(HMS)等,适应度函数用于建模优化目标。附带完整代码与运行结果展示。
165 24
|
6月前
|
人工智能 自然语言处理 算法
阿里云 AI 搜索开放平台:从算法到业务——AI 搜索驱动企业智能化升级
本文介绍了阿里云 AI 搜索开放平台的技术的特点及其在各行业的应用。
645 3
|
2月前
|
机器学习/深度学习 并行计算 算法
MATLAB实现利用禁忌搜索算法解决基站选址问题
MATLAB实现利用禁忌搜索算法解决基站选址问题
67 0
|
3月前
|
存储 搜索推荐 算法
加密算法、排序算法、字符串处理及搜索算法详解
本文涵盖四大类核心技术知识。加密算法部分介绍了对称加密(如 AES)、非对称加密(如 RSA)、哈希摘要(如 SHA-2)、签名算法的特点及密码存储方案(加盐、BCrypt 等)。 排序算法部分分类讲解了比较排序(冒泡、选择、插入、归并、快排、堆排序)和非比较排序(计数、桶、基数排序)的时间复杂度、适用场景及实现思路,强调混合排序的工业应用。 字符串处理部分包括字符串反转的双指针法,及项目中用正则进行表单校验、网页爬取、日志处理的实例。 搜索算法部分详解了二分查找的实现(双指针与中间索引计算)和回溯算法的概念(递归 + 剪枝),以 N 皇后问题为例说明回溯应用。内容全面覆盖算法原理与实践
132 0
|
8月前
|
机器学习/深度学习 算法
算法系列之搜索算法-深度优先搜索DFS
深度优先搜索和广度优先搜索一样,都是对图进行搜索的算法,目的也都是从起点开始搜索,直到到达顶点。深度优先搜索会沿着一条路径不断的往下搜索,直到不能够在继续为止,然后在折返,开始搜索下一条候补路径。
430 62
算法系列之搜索算法-深度优先搜索DFS
|
4月前
|
机器学习/深度学习 算法 数据可视化
基于Qlearning强化学习的机器人迷宫路线搜索算法matlab仿真
本内容展示了基于Q-learning算法的机器人迷宫路径搜索仿真及其实现过程。通过Matlab2022a进行仿真,结果以图形形式呈现,无水印(附图1-4)。算法理论部分介绍了Q-learning的核心概念,包括智能体、环境、状态、动作和奖励,以及Q表的构建与更新方法。具体实现中,将迷宫抽象为二维网格世界,定义起点和终点,利用Q-learning训练机器人找到最优路径。核心程序代码实现了多轮训练、累计奖励值与Q值的可视化,并展示了机器人从起点到终点的路径规划过程。
129 0

热门文章

最新文章