最基础也是最经典的查找算法之一，二分查找。
从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。–摘自维基百科
#实现思路： 🔗
根据上面摘自维基百科的原理，其实就很容易理解算法的思想，但是为了巩固记忆，我将整个内部计算的文字描述一下：
-
在数组 [1,2,3,4,5,6,7,8]中查找 数字 7
-
第一次查找如下: 用”()”表示低位和高位 ,用”[]”表示中间值 (1) 2 3 | [4] | 5 6 7 (8)
-
中间值为4 , 第二对比发现 数字大于中间值 , 低位提高 1 2 3 4 (5) [6] 7 (8)
-
中间值为6 , 第二对比发现 数字大于中间值 , 低位提高 1 2 3 4 5 6 ([7]) (8) #中间值为7 , 发现命中,返回下标
ok,下面用Go来实现一下:
// 二分查找 非递归版
func binarysearch3(arr []int, searchnum int) int {
low := 0 // 初始化低位 为列表头
height := len(arr) - 1 // 初始化高位 为列表尾
for low <= height { // 查找条件为: 低位小于或等于高位 , 否则会造成死循环
mid := (low + height) / 2 // 确认 中间值
if searchnum == arr[mid] { // 如果搜索的值 就是中间值,则返回下标
return mid
}
if searchnum > arr[mid] { // 如果搜索的值大于中间值, 说明搜索的值在中间值的右边
low = mid + 1 // 修改低位值为当前中间值,并忽略目前中间值 ( 因为已经匹配过了 )
}
if searchnum < arr[mid] { // 如果搜索的值大于中间值, 说明搜索的值在中间值的右边
height = mid - 1 // 修改低位值为当前中间值,并忽略目前中间值 ( 因为已经匹配过了 )
}
}
return -1
}
// 再来一个递归版的
// 递归版就不一行行注释,思路都是一样不过实现方式不同罢了。
func binarysearch2(arr []int, searchnum, low, height int) int {
mid := (low + height) / 2
if searchnum == arr[mid] {
return mid
}
if low > height {
return 0
}
if searchnum > arr[mid] {
return binarysearch2(arr, searchnum, height+1, height)
}
if searchnum < arr[mid] {
return binarysearch2(arr, searchnum, low, height-1)
}
return 0
}