数据结构之实现二分查找IP对应地区

学习极客时间《数据结构与算法之美》复杂二分的使用，使用 golang 实现了一个通过 IP 地址查找其所在地区的算法。

如下图，如果我要寻找处于泰州的一个 IP，那么在大量的数据段中，如何利用二分快速找到这个 IP 是泰州的 IP？

因为 IP 大都是分配给某个地区一段连续的地址，因此可以将此问题理解为，在一些有序的线段上寻找一个点的落点位置。

也就是说，我们可以以每一段的开始点为标志进行二分查找，假设我们的数据是从小到大排序的，找到第一个小于等于要查找的目标值的值，例如 IP 是泰州的，那么就需要找到泰州的 IP 段起始点，然后再去对比这个 IP 是否真的落在泰州的 IP 地址段内。

下面是具体代码：

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
package main

import (
	"errors"
	"fmt"
	"net"
	"strconv"
	"strings"
)

type tree struct {
	left  *tree
	right *tree
	value uint32
}

type ipArea struct {
	head       string
	tail       string
	areaName   string
	headUint32 uint32
	tailUint32 uint32
}

var ipAreas map[string]*ipArea
var uint32Ips []uint32

func init() {
	ipAreas = make(map[string]*ipArea)
	ipAreas["202.102.48.0"] = &ipArea{"202.102.48.0", "202.102.48.255", "江苏宿迁", 0, 0}
	ipAreas["202.102.49.15"] = &ipArea{"202.102.49.15", "202.102.51.251", "江苏泰州", 0, 0}
	ipAreas["202.102.56.0"] = &ipArea{"202.102.56.0", "202.102.56.255", "江苏连云港", 0, 0}
	ipAreas["202.102.133.0"] = &ipArea{"202.102.133.0", "202.102.133.255", "山东东营市", 0, 0}
	ipAreas["202.102.135.0"] = &ipArea{"202.102.135.0", "202.102.136.255", "山东烟台", 0, 0}
	ipAreas["202.102.156.34"] = &ipArea{"202.102.156.34", "202.102.157.255", "山东青岛", 0, 0}
	for headIP, area := range ipAreas {
		uint32Ips = append(uint32Ips, ipToUint32(headIP))
		area.headUint32 = ipToUint32(area.head)
		area.tailUint32 = ipToUint32(area.tail)
	}
	uint32Ips = mapSort(uint32Ips)
}

func main() {
	areaName, err := findIPArea("202.102.135.1")
	if err != nil {
		fmt.Println(err)
	} else {
		fmt.Println(areaName)
	}
}

func findIPArea(ip string) (string, error) {
	if net.ParseIP(ip).To4() == nil {
		return "", errors.New("param is error")
	}

	uint32IP := ipToUint32(ip)
	ipIndex := bsearchLastLTEUint32(uint32Ips, uint32IP)
	if ipIndex == -1 {
		return "", errors.New("not found ip area")
	}

	targetUint32IP := uint32Ips[ipIndex]
	targetIP := uint32ToIP(targetUint32IP)
	ipArea := ipAreas[targetIP]
	if ipArea.headUint32 <= uint32IP && uint32IP <= ipArea.tailUint32 {
		return ipArea.areaName, nil
	}
	return "", errors.New("not found ip area")
}

func ipToUint32(ip string) uint32 {
	var ret uint32
	s := strings.Split(ip, ".")
	for index, ipByte := range s {
		tmp, _ := strconv.Atoi(ipByte)
		ret += uint32(tmp) << ((3 - index) * 8)
	}
	return ret
}

func uint32ToIP(n uint32) string {
	return fmt.Sprintf("%d.%d.%d.%d", byte(n>>24), byte(n>>16), byte(n>>8), byte(n))
}

func bsearchLastLTEUint32(nums []uint32, target uint32) int {
	low := 0
	high := len(nums) - 1
	var middle int
	for low <= high {
		middle = (low + high) / 2
		switch {
		case nums[middle] <= target:
			if (middle == len(nums)-1) || (nums[middle+1] > target) {
				return middle
			}
			low = middle + 1
		case nums[middle] > target:
			high = middle - 1
		}
	}
	return -1
}

func mapSort(s []uint32) []uint32 {
	var root *tree
	for _, value := range s {
		root = add(root, value)
	}
	return appendValue(s[:0], root)
}

func add(node *tree, value uint32) *tree {
	if node == nil {
		node = &tree{value: value}
		return node
	}
	if value < node.value {
		node.left = add(node.left, value)
	} else {
		node.right = add(node.right, value)
	}
	return node
}

func appendValue(s []uint32, root *tree) []uint32 {
	if root != nil {
		s = appendValue(s, root.left)
		s = append(s, root.value)
		s = appendValue(s, root.right)
	}
	return s
}

二分查找变形问题

下面是一些变形问题的代码，供参考：

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
// 查找第一个值等于给定值的元素
func bsearchFirstEqual(nums []int, target int) int {
	low := 0
	high := len(nums) - 1
	var middle int
	for low <= high {
		middle = (low + high) / 2
		diff := nums[middle] - target
		switch {
		case diff == 0:
			if (middle == 0) || (nums[middle-1] != target) {
				return middle
			} else {
				high = middle - 1
			}
		case diff < 0:
			low = middle + 1
		case diff > 0:
			high = middle - 1
		}
	}
	return -1
}

// 查找最后一个值等于给定值的元素
func bsearchLastEqual(nums []int, target int) int {
	low := 0
	high := len(nums) - 1
	var middle int
	for low <= high {
		middle = (low + high) / 2
		diff := nums[middle] - target
		switch {
		case diff == 0:
			if (middle == len(nums)-1) || (nums[middle+1] != target) {
				return middle
			} else {
				low = middle + 1
			}
		case diff < 0:
			low = middle + 1
		case diff > 0:
			high = middle - 1
		}
	}
	return -1
}

// 查找第一个大于等于给定值的元素
func bsearchFirstGTE(nums []int, target int) int {
	low := 0
	high := len(nums) - 1
	var middle int
	for low <= high {
		middle = (low + high) / 2
		diff := nums[middle] - target
		switch {
		case diff < 0:
			low = middle + 1
		case diff >= 0:
			if (middle == 0) || (nums[middle-1] < target) {
				return middle
			} else {
				high = middle - 1
			}
		}
	}
	return -1
}

// 查找最后一个小于等于给定值的元素
func bsearchLastLTE(nums []int, target int) int {
	low := 0
	high := len(nums) - 1
	var middle int
	for low <= high {
		middle = (low + high) / 2
		diff := nums[middle] - target
		switch {
		case diff <= 0:
			if (middle == len(nums)-1) || (nums[middle+1] > target) {
				return middle
			} else {
				low = middle + 1
			}
		case diff > 0:
			high = middle - 1
		}
	}
	return -1
}
◀        
        ▶