二分查找数组配置

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

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

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

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

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

GO·NOTE

二分查找数组配置

性能测试