go中查找应用

野性酷女 2021-07-24 22:35 326阅读 0赞

# 一 点睛 #

在 Golang 中，常用的查找有两种。

**1 顺序查找**

**2 二分查找(该数组必须有序)**

# 二 顺序查找 #

## 1 需求 ##

有一个数列：白眉鹰王、金毛狮王、紫衫龙王、青翼蝠王

猜猜游戏：从键盘中任意输入一个名称，判断数列中是否包含此名称

## 2 代码 ##

package main
    
    import (
       "fmt"
    )
    
    func main() {
       // 思路
       // 1 定义一个数组：白眉鹰王、金毛狮王、紫衫龙王、青翼蝠王。字符串数组
       // 2 从控制台接收一个名字，依次比较，如果发现有，提示
       names := [4]string{"白眉鹰王", "金毛狮王", "紫衫龙王", "青翼蝠王"}
       var heroName = ""
       fmt.Println("请输入要查找的人名...")
       fmt.Scanln(&heroName)
       // 顺序查找:第1种方式
       for i := 0; i < len(names); i++ {
          if heroName == names[i] {
             fmt.Printf("找到%v , 下标%v \n", heroName, i)
             break
          } else if i == (len(names) - 1) {
             fmt.Printf("没有找到%v \n", heroName)
          }
       }
       // 顺序查找:第2种方式
       index := -1
       for i := 0; i < len(names); i++ {
          if heroName == names[i] {
             index = i // 将找到的值对应的下标赋给 index
             break
          }
       }
       if index != -1 {
          fmt.Printf("找到%v , 下标%v \n", heroName, index)
       } else {
          fmt.Println("没有找到", heroName)
       }
    }

## 3 测试 ##

请输入要查找的人名...
    白眉鹰王
    找到白眉鹰王 , 下标0
    找到白眉鹰王 , 下标0

# 三 二分查找 #

## 1 需求 ##

请对一个有序数组进行二分查找 \{1,8, 10, 89, 1000, 1234\} ，输入一个数看看该数组是否存在此数，并且求出下标，如果没有就提示"没有这个数"。

## 2 图解 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70][]

## 3 代码 ##

package main
    
    import (
       "fmt"
    )
    
    /*
    二分查找的思路: 要查找的数是 findVal
    1 arr是一个有序数组，并且是从小到大排序。
    2 先找到 中间的下标 middle = (leftIndex + rightIndex) / 2, 然后让中间下标的值和findVal进行比较。
    2.1 如果 arr[middle] > findVal ,  就应该在  leftIndex — (middle - 1) 这个范围查找
    2.2 如果 arr[middle] < findVal ,  就应该在  middel+1—rightIndex 这个范围查找
    2.3 如果 arr[middle] == findVal, 找到
    2.4 上面的2.1 2.2 2.3 的逻辑会递归执行
    3 退出递归的条件
    if  leftIndex > rightIndex {
       // 找不到..
       return ..
    }
    */
    // 二分查找的函数
    func BinaryFind(arr *[6]int, leftIndex int, rightIndex int, findVal int) {
       // 判断leftIndex 是否大于 rightIndex
       if leftIndex > rightIndex {
          fmt.Println("找不到")
          return
       }
    
    
       // 先找中间的下标
       middle := (leftIndex + rightIndex) / 2
       if (*arr)[middle] > findVal {
          // 说明查找的数在  leftIndex - middel-1 这个范围
          BinaryFind(arr, leftIndex, middle-1, findVal)
       } else if (*arr)[middle] < findVal {
          // 说明查找的数在  middel+1 - rightIndex 这个范围
          BinaryFind(arr, middle+1, rightIndex, findVal)
       } else {
          // 找到了
          fmt.Printf("找到了，下标为%v \n", middle)
       }
    }
    
    func main() {
       arr := [6]int{1, 8, 10, 89, 1000, 1234}
       BinaryFind(&arr, 0, len(arr)-1, 1000)
    }

## 4 测试 ##

> 找到了，下标为4

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70]: /images/20210724/da1ee8a8e4d141839645da13ab95f054.png