Golang实现二分查找法

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

思路

①先找到中间的下标middle = (leftIndex + RightIndex) /2 ,然后让中间的下标值和FindVal比较
a:如果arr[middle] > FindVal,那么就向LeftIndex~(midlle - 1)区间找
b:如果arr[middle] < FindVal,那么就向middle + 1 ~RightIndex区间找
c:如果arr[middle] == FindVal,那么直接返回
②从①的a、b、c递归执行，知道找到位置
③如果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 { BinaryFind(arr, leftIndex, middle - 1, findVal) } else if (*arr)[middle] < findVal { BinaryFind(arr, middle + 1, rightIndex, findVal) } else { fmt.Printf("找到了，下标是%vn", 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) }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//代码
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 {  
        BinaryFind(arr, leftIndex, middle - 1, findVal)
    } else if (*arr)[middle] < findVal {
        BinaryFind(arr, middle + 1, rightIndex, findVal)
    } else {
        fmt.Printf("找到了，下标是%vn", 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)
}

复制代码找到了，下标是6

1
找到了，下标是6