Go面试：实现二分查找（一个例子彻底弄懂）(Golang经典编程案例)

二分查找法 ： 就是实现在一组有序的数字数组集合中最快找到指定元素的下标

思路 ：

1. 先找到中间的下标middle = (leftIndex + RightIndex) /2 ,然后让中间的下标值和FindVal比较
   a:如果arr[middle] > FindVal,那么就向LeftIndex~(midlle - 1)区间找
   b:如果arr[middle] < FindVal,那么就向middle + 1 ~RightIndex区间找
   c:如果arr[middle] == FindVal,那么直接返回
2. 从①的a、b、c递归执行，知道找到位置
3. 如果LeftIndex > RightIndex，则表示找不到，退出

代码/举例 ：
假设说我要查找30这个值，如果按照循环的查找方法，找到30这个值要执行7次。那么如果是按照二分查找呢？二分查找的过程如下：

1. left = 1, right = 18; mid = (1+18)/2 = 9; 51 > 30

2. left = 1, right = mid - 1 = 8; mid = (1+8)/2 = 4; 15 < 30

3. left = mid + 1 = 5, right = 8; mid = (5+8)/2 = 6; 30 = 30 查找完毕

只需要执行3次，大大减少了执行时间

package main

import (
	"fmt"
)
//二分查找函数 //假设有序数组的顺序是从小到大（很关键，决定左右方向）
func BinaryFind(arr *[]int, leftIndex int, rightIndex int, findVal int)  {
	//判断 leftIndex是否大于rightIndex
	if leftIndex > rightIndex {
		fmt.Println("找不到")
		return
	}
	//先找到 中间的下标
	middle := (leftIndex + rightIndex) / 2

	if (*arr)[middle] > findVal {
		//要查找的数，范围应该在 leftIndex 到 middle+1
		BinaryFind(arr, leftIndex, middle-1, findVal)
	} else if (*arr)[middle] < findVal {
		//要查找的数，范围应该在 middle+1 到 rightIndex
		BinaryFind(arr, middle+1, rightIndex, findVal)
	} else {
		fmt.Printf("找到了，下标为：%v n", middle)
	}
}


func main() {
	//定义一个数组
	//arr := []int{1, 2, 5, 7, 15, 25, 30, 36, 39, 51, 67, 78, 80, 82, 85, 91, 92, 97}
	//BinaryFind(&arr, 0, len(arr) - 1, 30)

	arr := []int{2, 5, 7, 15, 25, 28, 30}
	BinaryFind(&arr, 0, len(arr) - 1, 7)
	fmt.Println("main arr=",arr)
}

执行结果如下图所示：

最后

以上就是大意短靴为你收集整理的Go面试：实现二分查找（一个例子彻底弄懂）(Golang经典编程案例)的全部内容，希望文章能够帮你解决Go面试：实现二分查找（一个例子彻底弄懂）(Golang经典编程案例)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。