如何优化两个有序结构体切片间的理想匹配搜索？

因为sliceA和sliceB已经按field1升序排序，我们可以利用二分查找快速定位每个A元素对应的B元素范围，将时间复杂度从O(n*m)降低到O(n log m)，大幅提升匹配效率。

核心思路 #

对于每个a在sliceA中：

1. 用二分查找找到sliceB中第一个满足field1 ≥ a.field1 - leftBorder的索引（左边界）
2. 用二分查找找到sliceB中最后一个满足field1 ≤ a.field1 + rightBorder的索引（右边界）
3. 遍历sliceB中左边界到右边界的元素，检查field2的匹配条件，符合则记录匹配关系

代码实现 #

import "sort"

type MyStruct struct {
	Id     int
	field1 int
	field2 int
}

func findMatches(sliceA, sliceB []*MyStruct, leftBorder, rightBorder int) [][2]*MyStruct {
	var matches [][2]*MyStruct
	bLen := len(sliceB)

	for _, a := range sliceA {
		minField1 := a.field1 - leftBorder
		maxField1 := a.field1 + rightBorder

		// 定位左边界：第一个field1 >= minField1的元素索引
		leftIdx := sort.Search(bLen, func(i int) bool {
			return sliceB[i].field1 >= minField1
		})

		// 定位右边界：第一个field1 > maxField1的元素索引，再减1得到最后一个符合条件的索引
		rightIdx := sort.Search(bLen, func(i int) bool {
			return sliceB[i].field1 > maxField1
		}) - 1

		// 遍历范围内元素，检查field2匹配条件（可根据实际需求调整判断逻辑）
		for i := leftIdx; i <= rightIdx && i >= 0; i++ {
			b := sliceB[i]
			if b.field2 >= a.field2-leftBorder && b.field2 <= a.field2+rightBorder {
				matches = append(matches, [2]*MyStruct{a, b})
			}
		}
	}

	return matches
}

效率提升原因 #

原双指针实现在最坏场景下（比如所有B元素都符合A的field1范围）依然是O(n*m)的时间复杂度。而二分查找定位范围的操作是O(log m)，每个A元素只需要遍历B中符合field1范围的子集，整体时间复杂度稳定在O(n log m)，当n和m较大时，性能提升非常显著。

额外优化方向 #

如果field2也可以提前排序（比如在sliceB中，同一field1范围内的元素按field2升序排列），还可以再次用二分查找定位field2的有效范围，进一步将内层遍历的时间复杂度从O(k)（k为范围内元素数量）降到O(log k)，不过这需要额外的预处理步骤。

内容的提问来源于stack exchange，提问作者Gasimoff