用Golang在一个自定义结构体切片上执行二分查找的程序

在这篇Golang文章中，我们将使用迭代和递归方法在一个自定义结构体切片上执行二分查找。二分查找是一种在排序后的元素序列中寻找特定值位置的查找算法。

算法

步骤1 − 首先，我们需要导入fmt包。
步骤2 − 创建一个自定义的Person结构，具有字符串类型的name和整数类型的age。
步骤3 − 现在，创建一个bSearch()函数，用于在Person结构体切片上执行二分查找。
步骤4 − 它将low和high变量初始化为切片的开始和结尾，然后循环继续，只要low小于或等于high。
步骤5 − 在循环的每次迭代中，它计算low和high之间的中点，并将该索引处的Person的name字段与键进行比较。
步骤6 − 如果name字段等于键，则函数返回索引。如果name字段小于键，则更新low为mid + 1。否则，更新high为mid – 1。
步骤7 − 开始main()函数。在main()函数内部，创建一个Person结构体切片和一个要搜索的键。
步骤8 − 现在，调用bSearch()函数，并将结构体和键作为参数传递给它。
步骤9 − 将结果消息打印到控制台。如果函数返回-1，则返回false，否则返回true。

示例1

在这个示例中，我们将定义一个bSearch()函数，使用迭代方法来在自定义结构体切片上执行二分查找。

package main

import "fmt"

type Person struct {
   name string
   age  int
}

func bSearch(people []Person, key string) int {
   l := 0
   h := len(people) - 1

   for l <= h {
      mid := (l + h) / 2

      if people[mid].name == key {
         return mid
      } else if people[mid].name < key {
         l = mid + 1
      } else {
         h = mid - 1
      }
   }
   return -1
}

func main() {
   people := []Person{
      {"Amy", 15},
      {"Bix", 20},
      {"Jim", 25},
      {"Ross", 40},
      {"Siri", 45},
   }

   key := "Siri"

   i := bSearch(people, key)

   if i == -1 {
      fmt.Printf("%s not found\n", key)
   } else {
      fmt.Printf("%s found at index %d\n", key, i)
   }
}

输出

Siri found at index 4

示例2

在这个示例中，我们将定义一个bSearch()函数，使用递归方法在一个自定义结构体切片上执行二分查找。

package main

import "fmt"

type Person struct {
   Name string
   Age  int
}

func bSearch(people []Person, target Person, low int, high int) int {
   if low > high {
      return -1
   }

   mid := (low + high) / 2
   if people[mid] == target {
      return mid
   } else if people[mid].Age < target.Age {
      return bSearch(people, target, mid+1, high)
   } else {
      return bSearch(people, target, low, mid-1)
   }
}

func main() {
   people := []Person{
      {"Angel", 10},
      {"Carie", 12},
      {"Simona", 15},
      {"John", 17},
      {"Sam", 20},
   }

   target := Person{"John", 17}
   index := bSearch(people, target, 0, len(people)-1)

   if index != -1 {
      fmt.Printf("%s found at index %d\n", target.Name, index)
   } else {
      fmt.Printf("%s not found\n", target.Name)
   }
}