Bug 4787 – std.algorithm.bisectRight()

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

The SortedRange primitives lowerBound, upperBound, trisect etc. should cover this. Please reopen if not.