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: -------