在数组中实现线性搜索算法的 R 程序


2023年4月28日, Learn eTutorial
3570

这是一个简单的 R 程序,用于检查数组元素中是否存在某个项目。这里我们将使用线性搜索算法/顺序搜索算法进行搜索。

什么是线性搜索?

线性搜索是用于在数组、列表或任何其他数据结构中搜索元素的基本方法。它也被称为顺序搜索,因为元素在列表中是按顺序搜索的。会有一个元素数组和一个要搜索的元素,以判断它是否属于给定的元素集。

顾名思义,线性搜索将搜索元素与数组元素从起始索引到最后一个逐一比较。如果找到匹配项,它将输出匹配项所在的数组索引,否则它将输出“在集合中未找到项目”。


与二分搜索不同,线性搜索广泛用于在无序列表(即包含未排序元素的列表)中搜索元素。尽管它适用于较小的列表(<100)。假设有一个包含 10,000 个元素的列表,并且搜索元素位于最后一个位置,顺序搜索将通过与列表中的每个元素进行比较来消耗大量时间。因此,线性搜索算法的最坏情况时间复杂度为 O(n)。

如何在 R 中实现线性搜索?

我们可以通过使用for 循环if 条件简单地实现此算法。

  • 首先,我们必须使用for 循环遍历数组元素。
  • for 循环的每次迭代中,将搜索元素与当前数组元素进行比较,然后 -
  • 如果元素匹配,则打印相应数组元素的索引,并将搜索标志设置为 1,然后跳出循环。
  • 如果元素不匹配,则继续下一个元素,直到数组末尾。
  • 最后,检查搜索标志是否仍为 0,即没有匹配项或给定数组中不存在搜索元素。

让我们通过一个示例来更好地理解,

  1. 这里我们取一个数组(6,5,3,9,4,8),我们需要搜索数字4是否存在于数组中。
    Linear Serach Algorithm
  2. 现在使用for 循环从起始索引(1)到最后一个遍历数组,并检查数组元素是否等于搜索元素 4。
    Linear Serach Algorithm
  3. 如果找到匹配项,则打印项目所在的数组索引,否则打印消息“未找到元素”。
    Linear Serach Algorithm

算法

步骤 1:使用 R 中一些预定义值初始化数组 arr
步骤 2:定义变量 item 为搜索值,flag 为零表示搜索状态。
步骤 3:启动一个从 1 到数组长度的for 循环,用于比较数组中的每个元素。
步骤 4:使用 if 条件 检查元素是否等于搜索元素,并且
步骤 5:如果条件为真,则打印当前数组索引并将标志更改为 1,标志值 1 表示我们在数组中找到了搜索元素,因此跳出for 循环
步骤 6:否则,for 循环将继续进行下一次迭代,直到数组结束。
步骤 7:检查if 标志值为 0,是则表示未找到元素。

R 源代码

                                          arr= c(6,5,3,9,4,8)                         #array of elements
item=4                                      #search element
flag=0                                      #search status value
for (i in 1:length(arr)){                   #array traversal
  if (arr[i] == item) {                     #check for match
    print(paste("element found at",i))
    flag=1
    break
  }
}
if(flag==0) print("element not found")
                                      

输出

[1] "element found at 5"

[Execution complete with exit code 0]