SIMD B-Search

BSeachVectorized.cs

// This seems to be actually broken huh
private static bool BSearchContainsCore(Span<int> haystack, int needle)
{
    // We could do better than to use divrem but stupid leetcode does not care for base latency
    // so we won't bother with it either, which is wrong but no one will thank you
    // for doing things properly anyway.
    var rem = haystack.Length % Vector<int>.Count;
    var vectors = MemoryMarshal.Cast<int, Vector<int>>(haystack[..^rem]);
    var scalars = haystack[^rem..];
    var needle = new Vector<int>(target);

    var lo = 0;
    var hi = vectors.Length - 1;
    ref var ptr = ref MemoryMarshal.GetReference(vectors);
    while (lo <= hi)
    {
        // Adapted from SpanHelpers.BinarySearch from CoreLib
        var idx = (int)(((uint)hi + (uint)lo) >> 1);
        var curr = Unsafe.Add(ref ptr, idx);

        // tfw no Aarch64 which has nice pairwise ops
        var gt = Vector.GreaterThanAll(needle, curr);
        var lt = Vector.LessThanAll(needle, curr);

        if (gt) lo = idx + 1;
        else if (lt) hi = idx - 1;
        else if (Vector.EqualsAny(needle, curr)) return true;
    }

    foreach (var scalar in scalars)
    {
        if (scalar == target) return true;
    }

    return false;
}