[Issue 4787] New: std.algorithm.bisectRight()

[d-bugmail]

http://d.puremagic.com/issues/show_bug.cgi?id=4787

           Summary: std.algorithm.bisectRight()
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: Phobos
        AssignedTo: nob...@puremagic.com
        ReportedBy: bearophile_h...@eml.cc


--- Comment #0 from bearophile_h...@eml.cc 2010-09-01 12:22:25 PDT ---
std.algorithm.findAmongSorted() is sometimes useful, but it doesn't cover all
usages. For example you may need to find the place where to insert a value
inside a sorted array of floating point values.

To this purpose it's useful a function similar to (a more generic version for
ranges may be written):


import std.stdio: writeln;

/**
Locate the proper insertion point for item in a sorted array to
maintain sorted order. If x is already present in arr, the
insertion point will be after (to the right of) any existing entries.
*/
int bisectRight(T)(T[] arr, T x) {
    int lo = 0;
    int hi = arr.length;
    while (lo < hi) {
        int mid = (lo + hi) / 2; // lo + hi may cause overflow!
        if (x < arr[mid])
            hi = mid;
        else
            lo = mid + 1;
    }
    return lo;
}

// demo ----------------
void main(string[] args) {
    auto array = [1.5, 3.2, 3.61, 11.0];
    assert(bisectRight(array, 0.0) == 0);
    assert(bisectRight(array, 4.1) == 3);
    assert(bisectRight(array, 50.5) == 4);
}


See also, for other quite useful ideas:
http://docs.python.org/library/bisect.html

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------