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 語言中解決此問題的三種不同方法。線性搜尋方法最簡單，但效率最低，而二分搜尋和遞迴二分搜尋方法效率更高，但稍微複雜一些。您可以根據切片的大小和目標元素出現頻率的預期選擇適合您用例的方法。