0%

二分查找数组配置

查找算法最简单直接的是暴力查找,如果对性能要求不高时间又紧张一时半会还想不好,那就用暴力吧,时间复杂度为 O(n)

如果细心的你发现数据是有顺序的,可以用二分查找,时间复杂度为 O(logN)

如果对性能要求特别高并且数据集是确定的,可以提前生成 hash 表,然后通过 hash 表来查找,时间复杂度为 O(1)。

注:如果数据量不大,请使用暴力算法,它是最优算法

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
package main

import (
"fmt"
"time"
)

// 暴力查找

func GetDegreeByViolence(price int) string {

if price >= 0 && price < 10 {
return "L"
}
if price >= 10 && price < 20 {
return "M"
}
if price >= 20 && price < 30 {
return "H"
}

return "N"
}

// 二分查找

type Item struct {
left int
right int
Degree string
}

var config = []*Item{
{0, 10, "L"},
{10, 20, "M"},
{20, 30, "H"},
}

func GetDegreeByBinary(price int) string {
start, end := 0, len(config)-1
mid := (start + end) / 2
for start <= end {
if price < config[mid].left {
end = mid - 1
} else if price >= config[mid].right {
start = mid + 1
} else {
return config[mid].Degree
}
mid = (start + end) / 2
}
return "N"
}

// hash 查找
var m = map[int]string{}

func init() {
for i := 0; i <= 30; i++ {
if i >= 0 && i < 10 {
m[i] = "L"
}
if i >= 10 && i < 20 {
m[i] = "M"
}
if i >= 20 && i < 30 {
m[i] = "H"
} else {
m[i] = "N"
}
}
}

func GetDegreeByHash(price int) string {
v, ok := m[price]
if !ok {
return "N"
}
return v
}

func main() {
CalculateTime(GetDegreeByViolence, 25, "violence")
CalculateTime(GetDegreeByBinary, 25, "Binary")
CalculateTime(GetDegreeByHash, 25, "Hash")
}

func CalculateTime(f func(int) string, price int, name string) {
startTime := time.Now()
for i := 0; i < 1000000; i++ {
f(price)
}
fmt.Println(name, "1000时间为:", time.Now().Sub(startTime))
}

结果:

1
2
3
violence 1000时间为: 1.9621ms
Binary 1000时间为: 3.9882ms
Hash 1000时间为: 10.9707ms

性能测试