C#中对存储定长排序键值对的byte[]执行Binary search的方法

有两种主流实现方式，优先推荐手动实现二分查找的方案，性能更高、灵活性更强。

方案1：手动实现二分查找（推荐） #

直接针对加载到内存的byte[]缓冲区编写二分逻辑，不需要额外做类型转换，适配任意定长键长和记录长度。
核心逻辑是直接按记录长度计算中间位置的偏移，对比键对应的字节段即可，参考实现代码如下：

/// <summary>
/// 定长记录二分查找
/// </summary>
/// <param name="buffer">加载了全部记录的字节缓冲区</param>
/// <param name="recordSize">单条记录的总长度（字节）</param>
/// <param name="keyLength">键的长度（字节）</param>
/// <param name="searchKey">要搜索的键的字节数组</param>
/// <returns>找到则返回记录的起始偏移，未找到返回负的插入位置，和.NET内置二分返回规则一致</returns>
public static int BinarySearchRecords(byte[] buffer, int recordSize, int keyLength, byte[] searchKey)
{
    if (buffer == null || buffer.Length % recordSize != 0)
        throw new ArgumentException("缓冲区长度不是单条记录长度的整数倍");
    if (searchKey == null || searchKey.Length != keyLength)
        throw new ArgumentException("搜索键长度和设定的键长不一致");

    int left = 0;
    int right = buffer.Length / recordSize - 1;

    while (left <= right)
    {
        int mid = left + (right - left) / 2; // 避免整数溢出
        int recordOffset = mid * recordSize;
        
        // 对比键字节段，用内置Span方法性能更高
        int compareResult = buffer.AsSpan(recordOffset, keyLength)
            .SequenceCompareTo(searchKey.AsSpan());

        if (compareResult == 0)
        {
            // 找到记录，如需直接返回对应int值，可替换为return BitConverter.ToInt32(buffer, recordOffset + keyLength);
            return recordOffset;
        }
        else if (compareResult < 0)
        {
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }

    return ~left;
}

如果要搜索的目标是字符串，只需要用对应编码（比如ASCII、UTF8）把字符串转成字节数组再传入searchKey参数即可。

方案2：封装结构适配Array.BinarySearch #

如果一定要使用.NET内置的Array.BinarySearch方法，需要先把字节缓冲区映射为自定义结构数组，再传入自定义比较器实现。
该方案需要处理结构序列化的问题，适配不同键长的灵活度更低，还会产生额外的内存拷贝，性能不如方案1。示例结构定义如下（以键长6为例）：

// 禁用字节对齐，保证结构内存布局和文件记录一致
[StructLayout(LayoutKind.Sequential, Pack = 1)]
public struct Record
{
    [MarshalAs(UnmanagedType.ByValArray, SizeConst = 6)]
    public byte[] Key;
    public int Value;
}

后续需要把byte[]缓冲区转换为Record[]数组，再实现IComparer<Record>接口传入Array.BinarySearch即可。

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