Go 实现二分查找的四个案例

In |

WechatIMG43.jpeg

案例一

  • 介绍

在一组数字类型的有序数组中，查询某个数字的数组下标。

  • 图解

二分查找案例一.gif

  • 创建 simple1.go 内容如下：
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
33
34
35
package main

import (
	"fmt"
)

func main() {
	// 需要查找的数字
	var targetNumb = 8
	// 目标有序数组
	arr := []int{1,2,3,4,5,6,7,8,9}
	var middle,low = 0,0
	var high = len(arr) - 1
	var isfind = 0

	for {
	    if low <= high {
	    	middle = (high + low) / 2
	    	if arr[middle] == targetNumb {
	    		fmt.Printf("%v 在数组中，下标值为：%v\n",targetNumb,middle)
	    		isfind = 1
	    		break
	    	} else if arr[middle] > targetNumb {
	    		// 说明该数在low-middle之间
				high = middle - 1;
	    	} else {
	    		// 说明该数在middle-high之间
				low = middle + 1;
	    	}
	    }
	}
	if isfind == 0 {
		fmt.Printf("数组不含 %v\n",targetNumb)
	}
}
  • 执行
1
2
$ go run simple1.go
8 在数组中，下标值为：7

案例二

  • 介绍

在一组经过任意位数的旋转后的数字类型的有序数组中，查询某个数字的数组下标。

  • 图解

二分查找案例二.gif

  • 创建 simple2.go 内容如下：
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
33
34
35
36
37
38
39
40
41
42
43
44
45
package main

import (
	"fmt"
	"encoding/json"
)

func main() {
	arr := []int{ 5, 6, 7, 8, 9, 0, 1, 2, 3, 4 }
	str,err := json.Marshal(arr)
    if err != nil {
        panic(err)
    }
    fmt.Printf("原始数据：%s\n",string(str))
	target := 7
	subscript := bs(arr, target, 0, len(arr)-1)
	fmt.Printf("数组下标：%v",subscript)
}

func bs(arr []int, target int, begin int, end int) int {
	if begin == end {
        if target == arr[begin] {
            return begin
        } else {
            return -1
        }
    }
    middle := (begin + end)/2
    if target == arr[middle] {
        return middle
    }
    if arr[begin] <= arr[middle-1] {
        if arr[begin] <= target && target <= arr[middle-1] {
            return bs(arr, target, begin, middle-1)
        } else {
            return bs(arr, target, middle+1, end)
        }
    } else {
        if arr[middle+1] <= target && target <= arr[end] {
            return bs(arr, target, middle+1, end)
        } else {
            return bs(arr, target, begin, middle-1)
        }
    }
}
  • 执行
1
2
3
$ go run simple2.go
原始数据：[5,6,7,8,9,0,1,2,3,4]
数组下标：2

案例三

  • 介绍

在一组数字类型的数组中，查询是否存在大于某个数字的数组元素。

  • 图解

二分查找案例三.gif

  • 创建 simple3.go 内容如下：
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
33
34
35
package main

import (
	"fmt"
)

func main() {
	// 需要查找大于的数字
	var targetNumb = 9
	// 目标有序数组
	arr := [10]int{-1, 3, 3, 7, 10, 14, 14}
	var middle,low = 0,0
	var high = len(arr) - 1
	var isfind = 0

	for {
	    if low <= high {
	    	middle = (high + low) / 2
	    	if arr[middle] > targetNumb && (middle == 0 || arr[middle - 1] <= targetNumb) {
	    		fmt.Printf("第一个比 %v 大的数字是 %v\n",targetNumb,arr[middle])
	    		isfind = 1
	    		break
	    	} else if arr[middle] > targetNumb {
	    		// 说明该数在 low～middle 之间
				high = middle - 1;
	    	} else {
	    		// 说明该数在 middle~high 之间
				low = middle + 1;
	    	}
	    }
	}
	if isfind == 0 {
		fmt.Printf("数组不含大于 %v 的数字\n",targetNumb)
	}
}
  • 执行
1
2
$ go run simple3.go
第一个比 9 大的数字是 10

案例四

  • 介绍

查找两个有序数组合并后的中位数。

  • 创建 simple4.go 内容如下：
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
package main
import (
    "fmt"
)

func main(){
    var nums1 = [6]int{1,2,3,4,5,6}
    var nums2 = [3]int{7,8,9}
    median := getMedian(nums1, 0, len(nums1)-1, nums2, 0, len(nums2)-1)
    fmt.Println(median)
}

func getMedian(a [6]int, begina int, enda int, b [3]int, beginb int, endb int) int {
    if enda - begina == 0 {
        if a[beginb] > b[beginb] {
            return b[beginb]
        } else {
            return a[beginb]
        }
    }
    if enda - begina == 1 {
        if a[begina] < b[beginb] {
            if b[beginb] > a[enda] {
                return a[enda]
            } else {
                return a[beginb]
            }
        } else {
            if b[beginb] < a[enda] {
                return a[begina]
            } else {
                return a[endb]
            }
        }
    }
    if endb-beginb < 2 {
        if (endb - beginb == 0) && (enda - begina)%2 != 0 {
            m := a[beginb]
            bb := b[(enda + begina)/2 - 1]
            c := b[(enda + begina)/2]
            if m < bb {
                return bb
            } else if m < c {
                return m
            } else {
                return c
            }
        } else if (endb - beginb == 0) && (enda - begina)%2 == 0 {
            m := a[beginb]
            c := b[(enda + begina)/2]
            d := b[(enda + begina)/2 + 1]
            if m < c {
                return c
            } else if m < d {
                return m
            } else {
                return d
            }
        } else {
            m := b[beginb]
            n := b[endb]
            bb := a[(enda + begina)/2 - 1]
            c := a[(enda + begina)/2]
            d := a[(enda + begina)/2 + 1]
            if n < bb {
                return bb
            } else if n > bb && n < c {
                return n
            } else if n > c && n < d {
                if m > c {
                    return m
                } else {
                    return c
                }
            } else {
                if m < c {
                    return c
                } else if m < d {
                    return m
                } else {
                    return d
                }
            }
        }
    } else {
        mida := (enda + begina)/2
        midb := (endb + beginb)/2
        if a[mida] < b[midb] {
            step := endb - midb
            return getMedian(a, begina + step, enda, b, beginb, endb - step)
        } else {
            step := midb - beginb
            return getMedian(a, begina, enda - step, b, beginb+ step, endb)
        }
    }
}
  • 执行
1
2
$ go run simple4.go
5
-------------本文结束感谢您的阅读-------------
0%