1.1.1. 一、在一个数组中查找一个数的方式。
找出一个数组arr中是否包含某个数value。可以有2种方式:
1、顺序查找:把value和arr数组中的每一个元素对比,最终找出值。
2、二分查找:先把数组安装从小到大排序。排序好之后使用二分查找。二分查找必须针对排序后的数组。
1.1.2. 二、二分查找的思想:
- 先找到数组中间的下标
middle = (leftIndex + rightIndex) / 2
。开始的时候leftIndex 就是0,rightIndex就是数组的最后一个元素的下标len(arr) - 1
- 然后让 中间下标的值
arr[middle]
和 value进行比较。 - 如 果 arr[middle] > value, 说明要找的值下标小于middle。 把rightIndex设置为(middle - 1);如 果 arr[middle] < value,就应该把leftIndex设置为(middle + 1);如果 arr[middle] == value, 就找到了。
递归循环上面的3步。如果leftIndex > rightIndex { // 找不到.. return .. }。
1.1.3. 三、二分查找的代码实现:
// 二分查找函数
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() {
intArr := [6]int{2,7,9,22,55,98}
BinaryFind(&intArr,0, len(intArr) - 1, 55)
}
说明:
上面用递归实现。把查找的值和
arr[middle]
比较,推动leftIndex 、rightIndex靠拢。rightIndex = middle - 1 或者 leftIndex = middle + 1 ;最后 leftIndex > rightIndex 。