编写一个 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 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始