Go 语言程序，用于在排序后的切片中查找目标元素的最后一次出现

---

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

使用线性搜索方法

在排序后的切片中查找目标元素最后一次出现的最简单方法是执行线性搜索。在这种方法中，我们从后向前遍历切片，直到找到目标元素。

算法

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

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

• 步骤 3 − 在函数内部使用 for 循环从后向前遍历切片。

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

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

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

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

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

示例

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

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

使用二分搜索方法

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

算法

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

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

• 步骤 3 − 在函数内部将 "start" 设置为 0，将 "end" 设置为切片长度 – 1。

• 步骤 4 − 当 "start" 小于或等于 "end" 时，将 "mid" 设置为 "start" 和 "end" 的平均值。

• 步骤 5 − 如果索引 "mid" 处的元素等于目标元素，则将 "lastIndex" 设置为 "mid"，并将 "start" 设置为 "mid + 1"。

• 步骤 6 − 否则，如果索引 "mid" 处的元素大于目标元素，则将 "end" 设置为 "mid - 1"。

• 步骤 7 − 否则，将 "start" 设置为 "mid + 1"，并返回 "lastIndex" 变量。

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

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

示例

在下面的示例中，我们将了解如何开发 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() 的函数，并使用排序后的切片 nums 和目标元素 target 调用 sort.SearchInts 函数。

• 如果返回的索引 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

结论

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