一.查找
1.概念
在一些数据元素中,通过一定的方法找出与给定的关键字相同的数据元素的过程.查找算法也可以叫搜索算法,查找算法就是从一个有序数列中找出一个特定的数，常用于判断某个数是否在数列中，或者某个数在数列中的位置。在计算机应用中，查找是常用的基本运算，是算法的重要组成部分
2. 列表查找
一个线性查找:从列表中查找指定的元素,由输入,输出两部分组成:
- 输入: 列表,待查找的元素
- 输出: 一般为元素的下标
二.查找的分类
1.顺序查找
顺序查找也叫线性查找（Linear Search）,逐个遍历数据集合，直到找到元素或搜索到元素最后一位,适用于小规模数据或无序数据的查找，时间复杂度为O(n),代码如下:
package mainimport "fmt"// 顺序查找函数
func linearSearch(arr []int, key int) int {for i, v := range arr {if v == key {return i // 返回找到的元素索引}}return -1 // 如果没有找到，返回-1
}func main() {// 测试数组arr := []int{1, 3, 5, 7, 9, 2, 4, 6, 8, 0}// 要查找的值key := 6// 执行顺序查找index := linearSearch(arr, key)if index != -1 {fmt.Printf("找到 %d 在索引 %d 的位置\n", key, index)} else {fmt.Printf("在数组中未找到 %d\n", key)}
}2.二分查找
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表中元素按关键字有序排列
package mainimport ("fmt"
)//二分查找的函数
/**
二分查找的思路分析: 需要查找的数是 findValue
1.arr是一个有序的数组,从小到大排序
2.先找到中间的下标middleIndex = (leftIndex + rightIndex) / 2, 然后让中间下标的值和findValue比较
2.1 如果arr[middleIndex] > findValue, 就应该向 leftIndex ~ middleIndex - 1方向查找
2.2 如果arr[middleIndex] < findValue, 就应该向 middleIndex + 1 ~ rightIndex 方向查找
2.3 如果arr[middleIndex] = findValue, 就找到了
2.4 上面的逻辑 2.1,2.2, 2.3 会递归执行
3.思考一下: 什么情况下就找不到了[分析出退出递归的条件]
if leftIndex > rightIndex {//找不到return ...
}
*/func BinaryFind(arr *[6]int, leftIndex int, rightIndex int, findValue int) {//判断leftIndex是否大于rightIndexif leftIndex > rightIndex {fmt.Printf("没有找到\n")return}//先找到中间的下标middleIndex := (leftIndex + rightIndex) / 2if (*arr)[middleIndex] > findValue {//说明要查找的数在leftIndex ~ middleIndex - 1 之间BinaryFind(arr, leftIndex, middleIndex - 1, findValue)} else if (*arr)[middleIndex] < findValue {//说明要查找的数在middleIndex + 1 ~ rightIndex 之间BinaryFind(arr, middleIndex + 1, rightIndex, findValue)} else {fmt.Printf("找到了, 下标为: %v\n", middleIndex)}
}func main() {arr := [6]int{1, 5, 8, 10, 23, 88}//测试BinaryFind(&arr, 0, len(arr) -1 , 23) //找到了, 下标为: 4
}
