Golang 在排序切片中找到目标元素的最后出现

在本文中，我们将学习如何编写一个Golang程序，使用线性搜索和二分搜索方法，在排序切片中找到目标元素的最后出现。我们将在本文中使用两个程序。在第一个程序中，我们将使用线性搜索方法，而在第二个程序中，我们将使用二分搜索方法实现结果。

使用线性搜索方法

找到排序切片中目标元素的最后出现的最简单方法是执行线性搜索。在这种方法中，我们从末尾开始迭代切片，直到找到目标元素。

步骤

• 步骤1 - 首先，我们需要导入fmt包。

• 步骤2 - 然后创建一个名为lastIndexOfLinear()的函数，它接受两个参数，一个是整数数组，另一个是要在数组中搜索的数字。

• 步骤3 - 在函数中使用for循环从末尾开始迭代切片。

• 步骤4 - 如果当前元素等于目标元素，则将”lastIndex”设置为当前索引。

• 步骤5 - 继续迭代，直到达到切片的开头，并返回lastIndex。

• 步骤6 - 现在，开始main()函数。在main()函数内，初始化一个整数数组并为其添加值。

• 步骤7 - 进一步，存储要搜索的元素，并将其与数组一起传递给上面创建的函数。

• 步骤8 - 将结果存储在一个变量中，并在屏幕上打印出来。

示例

以下示例演示了如何使用线性搜索方法开发Golang程序，以找到排序切片中目标元素的最后出现。

package main

import (
   "fmt"
)

func lastIndexOfLinear(nums []int, target int) int {
   for i := len(nums) - 1; i >= 0; i-- {
      if nums[i] == target {
         return i
      }
   }
   return -1
}

func main() {
   nums := []int{10, 20, 30, 40, 50}
   fmt.Println("The given array is:", nums)
   var target int = 40
   fmt.Println("The element to be searched is:", target)
   res := lastIndexOfLinear(nums, target)
   fmt.Println("The given element", target, "is present in the position:", res)
}

输出

The given array is: [10 20 30 40 50]
The element to be searched is: 40
The given element 40 is present in the position: 3

使用二分查找方法

二分查找是一种更高效的方法，用于在排序的切片中找到目标元素的最后一次出现。在这种方法中，我们将切片分成两半，并在可能包含目标元素的那一半中继续查找。

步骤

• 第一步 - 首先，我们需要导入fmt包。

• 第二步 - 然后创建一个名为lastIndexOfLinear()的函数，它接受两个参数，一个是整数数组，另一个是要在数组中搜索的数字。

• 第三步 - 在函数内部将”start”设置为0，将”end”设置为切片的长度-1。

• 第四步 - 当”start”小于或等于”end”时，将”mid”设置为”start”和”end”的平均值。

• 第五步 - 如果索引”mid”处的元素等于目标元素，则将”lastIndex”设置为”mid”，并将”start”设置为”mid + 1″。

• 第六步 - 否则，如果索引”mid”处的元素大于目标元素，则将”end”设置为”mid – 1″。

• 第七步 - 否则，将”start”设置为”mid + 1″，并返回”lastIndex”变量。

• 第八步 - 现在，开始main()函数并初始化整数数组以及要搜索的元素。

• 第九步 - 现在，通过传递所需的参数调用上述创建的函数，并将结果存储在一个变量中。

示例

在以下示例中，我们将了解如何使用二分查找方法开发go语言程序，以查找已排序切片中目标元素的最后一次出现。

package main

import (
   "fmt"
)

func binarySearchLastOccurrence(slice []int, target int) int {
   start := 0
   end := len(slice) - 1
   lastIndex := -1
   for start <= end {
      mid := (start + end) / 2
      if slice[mid] == target {
         lastIndex = mid
         start = mid + 1
      } else if slice[mid] > target {
         end = mid - 1
      } else {
         start = mid + 1
      }
   }
   return lastIndex
}

func main() {
   nums := []int{10, 2, 5, 40, 7}
   fmt.Println("The given array is:", nums)
   var target int = 5
   fmt.Println("The element to be searched is:", target)
   res := binarySearchLastOccurrence(nums, target)
   fmt.Println("The given element", target, "is present in the position:", res)
}

输出

The given array is: [10 2 5 40 7]
The element to be searched is: 5
The given element 5 is present in the position: 2

使用标准库函数

Go提供了一个名为sort.SearchInts的标准库函数，可用于在排序的切片中查找目标元素的最后一个出现。该函数在内部使用二分查找，返回第一个大于或等于目标元素的元素的索引。

步骤

• 首先我们需要导入fmt和sort包。

• 然后创建名为lastIndexOfStandard()的函数，并调用sort.SearchInts函数，参数为排序后的切片nums和目标元素target。

• 如果返回的索引i大于0且nums[i-1]等于目标元素，则返回i-1。否则返回-1。

• 现在调用main()函数。在main()函数内初始化数组以及要搜索的元素。

示例

在以下示例中，我们将了解如何使用标准库函数开发Go语言程序，以找到目标元素的最后一个出现。

package main

import (
   "fmt"
   "sort"
)

func lastIndexOfStandard(nums []int, target int) int {
   i := sort.SearchInts(nums, target)
   if i >= 0 && nums[i] == target {
      return i
   } else {
      return -1
   }

}

func main() {
   nums := []int{10, 20, 30, 40, 50}
   fmt.Println("The given array is:", nums)
   var target int = 40
   fmt.Println("The element to be searched is:", target)
   res := lastIndexOfStandard(nums, target)
   fmt.Println("The given element", target, "is present in the position:", res)
}

输出

The given array is: [10 20 30 40 50]
The element to be searched is: 40
The given element 40 is present in the position: 3

结论

在本文中，我们讨论了使用 Golang 解决这个问题的三种不同方法。线性搜索方法是最简单但效率最低的，而二分搜索和使用递归的二分搜索方法则更高效但稍微复杂一些。您可以根据切片的大小和目标元素出现的预期频率选择适合您的使用情况的方法。