为何存在已知性能差异的C#二分查找函数计时Ticks相近？

嘿，你已经把二分查找性能测试的核心组件都备齐了！我来帮你把这些东西串起来，顺利画出符合预期的性能图表～

第一步：完善测试逻辑，收集可靠数据 #

要验证log₂(n)-1和log₂(n)+1的复杂度趋势，你需要覆盖不同量级的数组大小，并且多次测试取平均值来避免单次波动。这里给你补全主函数的核心逻辑：

// 选择2的幂次作为数组大小，完美贴合log₂(n)的分析场景
var arraySizes = new List<int>();
for (int exp = 10; exp <= 20; exp++) // 从1024到1048576，覆盖足够的范围
{
    arraySizes.Add((int)Math.Pow(2, exp));
}

// 存储结果：键是数组大小，值分别是「存在目标键的平均耗时」和「不存在的平均耗时」
var performanceData = new Dictionary<int, (double AvgTimeWithKey, double AvgTimeWithoutKey)>();

const int TestRuns = 100; // 每个数组大小重复测试100次取平均
int target = YourGlobalTargetKey; // 你的全局目标键变量

foreach (int size in arraySizes)
{
    double totalTimeWithKey = 0;
    double totalTimeWithoutKey = 0;

    // 测试「存在目标键」的场景
    for (int i = 0; i < TestRuns; i++)
    {
        int[] sortedArray = arrayCreator(size, true); // 生成包含目标键的有序数组
        sw.Restart();
        _ = BinarySearch(sortedArray, target); // 调用你的二分查找实现
        sw.Stop();
        totalTimeWithKey += sw.Elapsed.TotalMicroseconds; // 用微秒更精准，避免小数位数过多
    }

    // 测试「不存在目标键」的场景
    for (int i = 0; i < TestRuns; i++)
    {
        int[] sortedArray = arrayCreator(size, false); // 生成不包含目标键的有序数组
        sw.Restart();
        _ = BinarySearch(sortedArray, target);
        sw.Stop();
        totalTimeWithoutKey += sw.Elapsed.TotalMicroseconds;
    }

    // 计算平均值并存入字典
    performanceData.Add(size, 
        (totalTimeWithKey / TestRuns, totalTimeWithoutKey / TestRuns));
}

第二步：数据可视化，画出性能曲线 #

有了数据之后，你可以用C#的可视化库（比如OxyPlot、WinForms Chart）或者把数据导出到Excel来画图。这里给你OxyPlot的示例代码，能直接生成对比图表：

using OxyPlot;
using OxyPlot.Series;
using OxyPlot.Axes;

// 创建图表模型
var plotModel = new PlotModel 
{ 
    Title = "二分查找性能对比：存在vs不存在目标键",
    LegendPosition = LegendPosition.RightTop
};

// 准备两条曲线的数据系列
var withKeySeries = new LineSeries 
{ 
    Title = "存在目标键 (理论复杂度: log₂(n)-1)",
    MarkerType = MarkerType.Circle,
    MarkerSize = 4
};

var withoutKeySeries = new LineSeries 
{ 
    Title = "不存在目标键 (理论复杂度: log₂(n)+1)",
    MarkerType = MarkerType.Diamond,
    MarkerSize = 4
};

// 填充数据点（X轴用log₂(n)，更直观展示线性趋势）
foreach (var entry in performanceData)
{
    int n = entry.Key;
    double logN = Math.Log2(n);
    double timeWith = entry.Value.AvgTimeWithKey;
    double timeWithout = entry.Value.AvgTimeWithoutKey;

    withKeySeries.Points.Add(new DataPoint(logN, timeWith));
    withoutKeySeries.Points.Add(new DataPoint(logN, timeWithout));
}

// 设置坐标轴
plotModel.Axes.Add(new LinearAxis 
{ 
    Position = AxisPosition.Bottom,
    Title = "log₂(数组大小n)",
    MajorGridlineStyle = LineStyle.Solid,
    MinorGridlineStyle = LineStyle.Dot
});

plotModel.Axes.Add(new LinearAxis 
{ 
    Position = AxisPosition.Left,
    Title = "平均耗时 (微秒)",
    MajorGridlineStyle = LineStyle.Solid,
    MinorGridlineStyle = LineStyle.Dot
});

// 添加曲线到图表
plotModel.Series.Add(withKeySeries);
plotModel.Series.Add(withoutKeySeries);

// 如果是WPF项目，把plotModel绑定到PlotView控件；WinForms则用PlotView控件加载

几个关键注意事项 #

• 务必保证数组有序：二分查找的前提是数组已排序，你的arrayCreator生成的数组必须是有序的，否则测试结果完全没有意义！
• 选择合适的计时单位：小数组耗时极短，用微秒（TotalMicroseconds）比毫秒更精准，避免出现大量0值
• 排除系统干扰：测试时关闭后台不必要的程序，尽量让CPU专注于测试任务，保证计时准确
• 对比理论值：你可以根据log₂(n)-1和log₂(n)+1生成理论曲线，和实际测试结果叠加，能更清晰地看到吻合度

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