【一 Go 到底】第三十一天 --- 查找

作者：指剑

2022-10-30
重庆
本文字数：1343 字
阅读完需：约 4 分钟

一、顺序查找

使用循环查找，遍历数组

1.1 顺序查找(方法一)

有一个存放名字的数列 names=["Alibe","Bob","Credly","Danni","Ella","翠花"],用户从键盘输入一个名称，判断该名称是否存在于数组内

// 顺序查找
package main
import "fmt"
func main() {
  // 定义数组  names := []string{"Alibe", "Bob", "Credly", "Danni", "Ella", "翠花"}
  // 定义用户输入变量  var name string  // 获取用户输入  fmt.Printf("请输入用户名: ")  fmt.Scanln(&name)
  for i := 0; i < len(names); i++ {    if name == names[i] {      //请输入用户名: Bob      // Bob 存在, 下标=1      fmt.Printf("%v 存在, 下标=%v", name, i)      break    } else if i == len(names)-1 {      fmt.Printf("%v不存在......", name)      break    }  }}

复制代码

1.2 顺序查找(方法二)

// 顺序查找
package main
import "fmt"
func main() {
  // 定义数组  names := []string{"Alibe", "Bob", "Credly", "Danni", "Ella", "翠花"}
  // 定义用户输入变量  var name string  // 获取用户输入  fmt.Printf("请输入用户名: ")  fmt.Scanln(&name)
  // 定义下标变量  index := -1
  for i := 0; i < len(names); i++ {    if name == names[i] {      index = i      break    }  }  if index != -1 {    fmt.Printf("%v存在，对应下标=%v", name, index)  } else {    fmt.Printf("%v不存在...", name)  }}

复制代码

二、二分查找(该数组必须是有序的)

需要是有序数组，并且从小到大排序
先找到中间下标 middle_index = (left_index + right_index)/2,让要查找的值-findVal与中间下标的值进行对比-midVal

midVal>findVal,就应该向 left_Index 到(middle_index-1)区间查找，也就是左边到中间这块区间
midVal>findVal,就应该向 (middle_index+1)到 right_Index 区间查找，也就是中间到右边这块区间
midVal==findVal,就刚好找打这个数

如果 left_Index>right_Index 就退出

2.1 二分查找案例一

对一个有序数组进行二分查找，[1, 8, 18, 108, 1008, 1888],输入一个数，查看该数是否存在于数组中，若存在，请输入该数在数组中的下标，若不存在，则提示"不存在"


// 二分查找
package main
import "fmt"
func binarySearch(arr *[]int, leftIndex int, rightIndex int, findVal int) {  // 判断leftIndex是否大于rightIndex  if leftIndex > rightIndex {    fmt.Println("找不到该数")    return  }  // 中间下标  midIndex := (leftIndex + rightIndex) / 2
  if (*arr)[midIndex] > findVal {    // 调用函数进行查找    // 要查找的数在左边    binarySearch(arr, leftIndex, midIndex-1, findVal)  } else if (*arr)[midIndex] < findVal {    // 要查找的数在右边    binarySearch(arr, midIndex+1, rightIndex, findVal)  } else if (*arr)[midIndex] == findVal {    fmt.Printf("找到了,数组下标=%v", midIndex)  }}
func main() {  // 定义有序数组  nums := []int{1, 8, 18, 108, 1008, 1888}
  // 定义用户输入变量 num  var num int  // 获取用户输入  fmt.Printf("请输入您要查找的数: ")  fmt.Scanln(&num)
  binarySearch(&nums, 0, len(nums)-1, num)
}