查找算法选择
在查找已排序数组中的某个值时，有线性查找和二分查找等算法。线性查找是逐个遍历数组元素，C++ 里用 `std::find` 函数实现。对于大型数组，二分查找更出色，它通过持续将搜索区间一分为二定位目标值，C++ 中 `std::binary_search` 函数实现该算法。流行的 Roaring Bitmap 格式检查值是否存在时常用二分查找。
SIMD Quad 算法的启发与实现
为找更快查找方法，得到两点启发：一是现代处理器有数据并行指令（SIMD），可同时检查多个值；二是现代处理器内存级并行性好，可尝试四叉查找。基于此研发出 SIMD Quad 算法，它结合四叉插值查找与 SIMD 技术，将数组划分为含 16 个元素的块，以块的最后一个元素为插值键缩小搜索范围，再用 SIMD 指令检查块内元素。其核心是分层搜索，先在块边界用插值查找，再在块内用 SIMD 并行检查。具体步骤包括初始检查、块划分、四叉插值查找、块选择、SIMD 检查和剩余元素检查。
基准测试结果
进行基准测试，针对数组大小从 2 到 4096 个元素，生成 100,000 个已排序的 16 位无符号整数数组，分别进行 1000 万次“冷”模式和“热”模式的成员查询，测量线性搜索、二分搜索和 SIMD Quad 算法的平均查询时间。用搭载 Apple LLVM 的 Apple M4 和搭载 GCC 的 Intel Emeral Rapids 处理器测试。结果显示，数组规模变大时，二分搜索性能优于线性搜索；SIMD Quad 算法在 Intel 和 Apple 平台表现差异显著，但在所有情况下都比二分搜索快。该算法的 SIMD 部分简单能提速，四叉方法在 Intel 平台对大型数组且缓存未命中情况是不错的优化方式。
相关链接与结论
源代码可在 GitHub 上获取。结论表明，教科书上的二分查找虽不错，但可采用更有效方法，SIMD Quad 算法试图利用内存级和数据并行性，还有进一步优化空间。此外还提供了延伸阅读链接。
附录：源代码
给出了 `simd_quad` 函数的源代码。
关于作者与文章信息
作者 Daniel Lemire 是魁北克大学（TELUQ）的计算机科学教授。文章发布于 2026 年 4 月 27 日 - 2026 年 4 月 28 日。
评论
有 Scott Myron、[purplesyringa]、Sam Mason、Walter 等人的评论及回复，涉及对文章内容的疑问、其他数据结构的讨论和测试结果分享等。
