Golang 对自定义struct切片执行二分查找

在这篇Golang文章中，我们将使用迭代和递归方法对自定义struct切片执行二分查找。二分查找是一种用于在排序的元素序列中找到特定值位置的搜索算法。

步骤

步骤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()函数，并将struct和关键字作为参数传递给它。
步骤9 − 将结果消息打印到控制台。如果函数返回-1，则返回false；否则返回true。

示例1

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

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)
   }
}