A mathematically exact, correction-free search algorithm using power-of-two stepping with virtual list length adjustment for sorted datasets,

[fredhar]

A mathematically exact, correction-free search algorithm using power-of-two stepping with virtual list length adjustment for sorted datasets

Proposal: Pure Power-of-Two Based Search Algorithm for Sorted Lists

Dear .NET Platform Developers,

I am an independent software developer with a long history of designing efficient algorithms for data structures.
I would like to offer you an innovative search method that I have successfully used in my own projects. This method is conceptually simple, mathematically exact, and particularly suited for sorted lists where jump-based access is important.

Key Features of the Algorithm

• No boundary tracking (no low/high management)
• Pure bit-shift logic based on powers of two
• Exact convergence without correction at the end
• Always returns a valid list element, clearly indicating whether an exact match was found
• Suitable for performance-critical search tasks in sorted structures

Sample C# Implementation

internal static (bool found, SpacePoint sp) pwrSearch(this GrafiekOpbouw opbouw, long t)
{
    var lijst = opbouw.KoersLijst;
    int n = lijst.Count - 1;
    int k = 2;

    while (n > k - 1) k <<= 1;
    k >>= 1;

    int index = k - 1;
    bool found = false;

    while (!found && k != 1)
    {
        prevIndex = index;

        if (t > lijst[index].Time)
        {
            k >>= 1;
            index -= k;
        }
        else if (t < lijst[index].Time)
        {
            k >>= 1;
            index += k;
            while (index > n - 1)
            {
                k >>= 1;
                index -= k;
            }
        }
        found = lijst[index].Time == t;
    }

    var record = lijst[index];
    return (found, new SpacePoint(index, record.Time, record.Mean));
}

Closing Remarks

I hereby offer this method to you without any restrictions or obligations, hoping that you may find it useful for further exploration or even consider including it in the .NET standard library or Visual Studio tooling.

I am available for further explanation if needed.

Kind regards,
Fred Harthoorn
GitHub: @fredhar

[gfoidl]

mathematically exact

Can you provide the proof / paper which demonstrates the correctness?