Go sort.Search 在降序切片上怎么写正确的判断函数

我第一次把降序切片交给 sort.Search 时，直觉是照搬升序写法：data[i] >= target。结果谓词不再保持“前面全是 false、后面全是 true”，返回位置自然不可信。正确做法是保留原数据顺序，把判断改成 data[i] 。例如 []int{55, 45, 36, 28, 21, 15, 10, 6, 3, 1} 查找 6 时，返回索引 7。

先把 sort.Search 的返回语义看明白

sort.Search(n, f) 假设 f 在索引范围内呈现一个单调形状：前面可以是若干个 false，后面只能是 true。它返回后半段的第一个索引；如果整个范围都是 false，就返回 n。这也是为什么返回值不能直接拿来下标访问。

升序数据中，查找第一个大于等于目标值的位置通常写 data[i] >= target。降序数据的数值随着索引增大而变小，同一个边界会反过来：较大的前缀仍然大于目标，较小的后缀才满足小于等于目标，因此谓词应当写成 data[i] 。

降序切片的判断函数应该怎么改

下面的辅助函数返回“第一个小于或等于 target 的位置”。它不修改原切片，也不需要先反转数据。

package main

import "sort"

// firstLessOrEqualDescending 返回降序切片中第一个小于等于 target 的索引。
// 如果所有元素都大于 target，返回 len(data)，调用方不能直接访问 data[i]。
func firstLessOrEqualDescending(data []int, target int) int {
	// 降序数据的后缀越来越小，所以用 

以目标值 6 为例，前面的 55、45、36、28、21、15、10 都不满足条件，索引 7 的 6 第一次满足，后面的 3 和 1 也继续满足。这个“前 false、后 true”的形状正是二分查找需要的单调谓词。

正确处理命中、未命中和重复值

如果业务要求的是精确查找，返回索引后要先判断范围，再比较元素值；如果业务要的是插入边界或第一个不超过阈值的位置，则可以直接使用这个索引。

// findExactDescending 在降序切片中查找精确值，找不到时返回 false。
func findExactDescending(data []int, target int) (int, bool) {
	i := firstLessOrEqualDescending(data, target)
	// i 可能等于 len(data)，先做范围判断再读取 data[i]。
	if i == len(data) || data[i] != target {
		return 0, false
	}
	return i, true
}

有重复值时，函数返回的是从左到右第一个满足 的位置，也就是降序排列中更靠前的边界。例如 [10, 8, 8, 8, 3] 查找 8，会得到第一个 8 的索引，而不是最后一个 8。如果目标大于等于首元素，结果可能是 0；如果目标小于尾元素，结果就是 len(data)。

不要把升序辅助函数和降序数据混用

sort.SearchInts 以及常见的 data[i] >= target 示例默认面向升序切片。降序切片不能只替换数据而保留这个谓词，否则可能得到一个看似合法、实际错误的索引。若输入顺序来自外部，应该在进入查询边界前由调用方保证降序；需要诊断时可以使用与排序方向一致的比较函数检查相邻元素。

还要把“第一个不超过阈值”和“精确找到目标”分开设计：前者允许返回插入位置，后者必须在 i 后检查 data[i] == target。这两个结果都来自同一次二分查找，但业务含义不同。

常见问题

目标值比降序切片的最大值还大时返回什么？

返回 0，因为首个元素已经满足小于等于目标值。使用前要先确认 0 是否代表业务上的有效位置。

目标值比所有元素都小时为什么返回 len(data)？

因为没有元素满足 data[i] 。len(data) 是“应插入到末尾”或“没有候选”的边界标记，不是有效元素索引。

可以先把切片反转再调用升序写法吗？

可以，但会改变数据顺序或引入额外切片成本。只需要查询边界时，直接为降序数据写 更清楚，也能保留原切片。