Golang 实现线性搜索算法

在编程中，要从数组、链表或其他数据结构中搜索任何内容，我们有几种搜索算法，其中之一是线性搜索。在线性搜索中，我们从开始迭代数据结构，并搜索元素直到最后一个索引。

线性搜索算法的优点是我们可以对排序和未排序的数据执行此搜索。缺点是对于排序或未排序的数据，查找元素需要相同的时间。

例如，我们有一个元素数组{10, 5, 3, 7, 6, 12}，我们要查找元素3，那么在线性搜索算法中，我们将：

• 首先与索引0上的10进行比较，因为值不相等，所以移动到下一个索引

• 现在，我们将5与3进行比较，因为两者都不相等，所以移动到下一个索引

• 现在我们在索引2处找到了元素

步骤

步骤1： 使用import关键字在顶部导入所需的包。

步骤2： 然后，主要函数将首先被执行。

• 首先，我们声明并初始化数组。

• 通过将数组、大小和要在参数中搜索的元素传递给linearSearch()函数来搜索元素。

• 最后，打印结果，判断元素是否存在。

步骤3.1： 在linearSearch()函数中

• 第一种方法，我们在数组上运行一个for循环。

• 在循环内部，我们将元素与当前索引处的值进行比较。如果值匹配，则返回索引。

• 最后，如果元素不在数组中，则返回-1。

步骤3.2： 在linearSearch()函数中

• 第二种方法是递归函数。

• 基本条件是当前索引应小于数组的大小，否则返回-1。

• 如果当前索引处的值等于我们要查找的值，则返回索引。

示例1

在此示例中，我们通过在从数组的第0个索引到最后一个索引的循环中运行线性搜索来实现线性搜索。在每个索引上，我们将当前索引元素与我们要搜索的元素进行比较，如果两个元素匹配，则返回索引。

package main

import "fmt"

// function to print the array with array and
// size of the array as argument
func printArray(array []int, size int) {
    for i := 0; i < size; i++ {
        fmt.Print(array[i], " ")
    }
    fmt.Println()
}

// linear function to find an element in the array
func linearSearch(array []int, size int, toFind int) int {
    // running for loop over the array
    for i := 0; i < size; i++ {
        //Comparing the current index value with the
        // value we want to find
        if array[i] == toFind {
            return i
        }
    }

    // returning -1 if value not present in the array
    return -1
}

func main() {
    // declaring and initializing the
    // array using the shorthand method
    array := []int{10, 5, 3, 7, 6, 12}

    // declaring and initializing the
    // variable using the var keyword
    var toSearch int
    toSearch = 3

    fmt.Println("Golang program to find an element in an array using linear search.")
    fmt.Print("array:")
    printArray(array, 6)
    // linear search function passing array and
    // variable as a parameter
    index := linearSearch(array, 6, toSearch)

    if index == -1 {
        fmt.Println(toSearch, "is not present in the array.")
    } else {
        fmt.Println(toSearch, "is present at index 2  in the array.")
    }
}

输出

元素存在。

Golang program to find an element in an array using linear search.
array: 10 5 3 7 6 12 
3 is present at index 2 in the array.

示例2

在这个示例中，我们将使用递归方法来实现线性搜索。在递归调用中，我们将在每个函数调用中增加索引。在每个函数调用中，我们将当前索引元素与我们要搜索的元素进行比较，如果两个元素匹配，则返回索引。

package main

import "fmt"

// function to print the array with array and
// size of the array as argument
func printArray(array []int, size int) {
    for i := 0; i < size; i++ {
        fmt.Print(array[i], " ")
    }
    fmt.Println()
}

// linear function to find an element in the array
func linearSearch(array []int, currIndex int, size int, toFind int) int {
    if currIndex >= size {
        // returning -1 if value not present in the array
        return -1
    }

    //Comparing the current index value with the
    // value we want to find
    if array[currIndex] == toFind {
        return currIndex
    }

    // calling linearSearch function for the next index
    return linearSearch(array, currIndex+1, size, toFind)
}

func main() {
    // declaring and initializing the
    // array using the shorthand method
    array := []int{10, 5, 3, 7, 6, 12}

    // declaring and initializing the
    // variable using the var keyword
    var toSearch int
    toSearch = 3

    fmt.Println("Golang program to find an element in an array using linear search recursively.")
    fmt.Print("array:")
    printArray(array, 6)
    // linear search function passing array and
    // variable as a parameter
    index := linearSearch(array, 0, 6, toSearch)

    if index == -1 {
        fmt.Println(toSearch, "is not present in the array.")
    } else {
        fmt.Println(toSearch, "is present at index 2 in the array.")
    }

}

输出

Golang program to find an element in an array using linear search recursively.
array: 10 5 3 7 6 12 
3 is present at index 2 in the array.

结论

这是在Golang中执行线性搜索的两种方法。第二种方法有多个函数调用，对于具有大量元素的数组，堆栈将超载。对于一个简单的操作来说，这不是一种适当的编程方式，因此使用循环的方法将是更高效的实现方式。要了解更多关于Golang的信息，您可以探索这些 教程 。