編寫一個 Golang 程式來搜尋排序陣列中元素

解決此問題的思路

• 步驟 1: 從第 0 個索引到 n - 1 遍歷陣列，其中 n 是給定陣列的大小。
• 步驟 2: 宣告 low = 第 0 個索引 且 high = n - 1。啟動一個 for 迴圈，直到 low 小於 high。
• 步驟 3: 查詢 mid = (low + high) / 2，如果中間的元素等於 key，則返回 mid 索引。
• 步驟 4: 如果 mid 處的元素大於 key，則令 high = mid。
• 步驟 5: 如果 mid 處的元素小於 key，則令 low = mid + 1。
• 步驟 6: 如果給定陣列中不存在 key，則返回 -1。

時間複雜度: log₂(n)

程式

即時演示

package main
import "fmt"
func binarySearch(arr []int, key int) int{
   high := len(arr) - 1
   low := 0
   var mid int
   for low <= high {
      mid = (high+low)/2
      if arr[mid] == key {
         return mid
      } else if arr[mid] > key {
         high = mid
      } else {
         low = mid + 1
      }
   }
   return -1
}

func main(){
   fmt.Println(binarySearch([]int{1, 4, 6, 8, 9, 10}, 11))
   fmt.Println(binarySearch([]int{1, 4, 6, 8, 9, 10}, 8))
   fmt.Println(binarySearch([]int{1, 4, 6, 8, 9, 10}, 10))
}

輸出

-1
3
5

Kiran P

更新於: 2021 年 2 月 4 日

508 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始