为何Go的slices.BinarySearchFunc会两次调用匹配元素的比较函数？

我在调试传入slices.BinarySearchFunc的比较函数时，发现匹配元素的日志被打印了两次，对此感到好奇。

复现代码 #

package main

import (
    "cmp"
    "log"
    "slices"
    "testing"

    "github.com/stretchr/testify/assert"
)

func init() {
    log.SetFlags(0)
}

func Test(t *testing.T) {
    numbers := []int{
        1, 2, 3,
    }
    timesCalled := 0
    comparisonFunc := func(l, r int) int {
        timesCalled++
        log.Printf("Comparing %d and %d", l, r)
        result := cmp.Compare(l, r)
        if result == 0 {
            log.Printf("Matched %d and %d", l, r)
        }
        return result
    }
    if idx, found := slices.BinarySearchFunc(numbers, 2, comparisonFunc); found {
        assert.Equal(t, 2, numbers[idx])
    } else {
        assert.Fail(t, "Number not found")
    }
    assert.LessOrEqual(t, timesCalled, 2)
}

输出结果 #

=== RUN   Test
Comparing 2 and 2
Matched 2 and 2
Comparing 1 and 2
Comparing 2 and 2
Matched 2 and 2
    prog_test.go:35: 
            Error Trace:    /tmp/sandbox3165947586/prog_test.go:35
            Error:          "3" is not less than or equal to "2"
            Test:           Test
--- FAIL: Test (0.00s)
FAIL

Program exited.

问题解答 #

1. 该行为是否符合预期？ #

是，这个行为完全符合预期。slices.BinarySearchFunc的底层实现遵循标准二分查找逻辑，其设计目标是返回第一个匹配元素的索引（当数组存在多个相同元素时）。因此，即使在中间步骤找到匹配项，算法仍会继续调整左右边界，确认左半部分是否存在更早的匹配元素，这就导致了比较函数被多次调用。

在你的测试用例中，目标元素2位于数组中间，第一次匹配后，算法会继续检查左半区间，因此触发了第二次比较调用。

2. 能否让比较函数找到匹配后立即停止？ #

无法通过标准库的slices.BinarySearchFunc实现这一点，因为该函数必须完成完整的边界确认流程来保证返回索引的正确性。

如果你的场景仅需要快速判断元素是否存在，不需要定位第一个匹配项，可以自行实现简化版的二分查找，在首次匹配时直接返回结果：

func quickBinarySearchFunc[S ~[]E, E any](x S, target E, cmp func(E, E) int) (int, bool) {
    low, high := 0, len(x)
    for low < high {
        mid := (low + high) / 2
        c := cmp(x[mid], target)
        if c == 0 {
            return mid, true
        } else if c < 0 {
            low = mid + 1
        } else {
            high = mid
        }
    }
    return low, false
}

注意：这个简化版本在存在多个相同元素时，返回的可能不是第一个匹配项的索引，仅适用于只需要确认存在性的场景。

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