On Monday, 7 December 2020 at 06:24:27 UTC, drug wrote:
Phobos provides this by SortedRange:
https://dlang.org/phobos/std_range.html#.SortedRange
Example of usage:
https://run.dlang.io/is/WW2bn0
Thanks!
:-)
Phobos provides this by SortedRange:
https://dlang.org/phobos/std_range.html#.SortedRange
Example of usage:
https://run.dlang.io/is/WW2bn0
ines.binarySearchLow( 21 ); // 0 - near lowest
index
Where is the implementation of "binary search", please?
On Sunday, 25 February 2018 at 21:18:55 UTC, Joel wrote:
The number tests work, but not the string one.
Thanks guys. I worked it out, I thought my search code was right,
since the first asserts worked.
On 2/25/18 4:32 PM, Seb wrote:
Also note that Phobos comes with binary search built-in:
---
assert([1,2,3,4,5,6,7,8,9,10,11].assumeSorted.canFind(6));
---
https://run.dlang.io/is/bfpBpA
canFind (and find) works even on non-sorted ranges, so it's not the
greatest proof. But it'
/ The current element is higher than the needle -> you need to
go to the left, not right
--
-> Swap them.
Also note that Phobos comes with binary search built-in:
---
assert([1,2,3,4,5,6,7,8,9,10,11].assumeSorted.canFind(6));
---
https://run.dlang.io/is/bfpBpA
On 02/25/2018 10:18 PM, Joel wrote:
if (arr[i] > n)
arr = arr[i + 1 .. $];
When `arr[i]` is greater than `n`, then the values in `arr[i + 1 .. $]`
will only be even greater. You're picking the wrong half of the array.
The number tests work, but not the string one.
void main() {
assert([1,2,3,4,5,6,7,8,9,10,11].binarySearch(6));
assert(! [1,2,3,4,5,7,8,9,10,11].binarySearch(6));
assert("abcdefghijklmnopqrstuvwxyz".binarySearch('j')); // not
work
import std.stdio;
writeln("Assert tests
On Sunday, 21 January 2018 at 20:46:56 UTC, Timon Gehr wrote:
On 21.01.2018 21:20, Mark wrote:
Just realized that I commented out the creation of the BST
new link: https://dpaste.dzfl.pl/ce620cbee919
'in' means 'const scope', but it seems you need references that
are allowed to mutate the i
On 21.01.2018 21:20, Mark wrote:
Just realized that I commented out the creation of the BST
new link: https://dpaste.dzfl.pl/ce620cbee919
'in' means 'const scope', but it seems you need references that are
allowed to mutate the incoming items. Remove the 'in' attribute from the
parameters a
Just realized that I commented out the creation of the BST
new link: https://dpaste.dzfl.pl/ce620cbee919
Hello,
I re wrote my old BST. This one is far more complete and clean.
However, It fails my final unittest when I try to stick a class
in as its type.
Link: https://dpaste.dzfl.pl/95e1ae49b25b
Ive done this type of thing before, but it is giving me this
error:
BinarySearchTree.d(30): Erro
ad will be completely dwarfed
by the actual search (assuming your array is big enough to
justify binary search over linear search). If your array
contains duplicates but you are only interested in getting any
one of them, or your comparison is non-trivial, then I agree
this could potentially be a pr
On Tuesday, 15 December 2015 at 00:31:45 UTC, Jakob Ovrum wrote:
For sorted arrays you won't find any other standard facility
for doing binary search, but the containers RedBlackTree and
BinaryHeap provide something related.
You could also get the upper bound (SortedRange.upperBound
doesn't contain duplicates, the overhead is just
one extra comparison. For cheap comparisons, this overhead will
be completely dwarfed by the actual search (assuming your array
is big enough to justify binary search over linear search). If
your array contains duplicates but you are
Is there no way to do a simple binary search of a sorted array
using Phobos?
I found `SortedRange.contains`, but that just returns true/false.
I want the index of the element, or the element itself.
I also found `SortedRange.equalRange`, but that sounds like it
has an unreasonable amount of
I think I found solution using opBinaryRight
import std.range;
struct S
{
int i;
string s;
int opCmp(int i) {
return this.i - i;
}
int opCmp(ref const S s) {
return this.i - s.i;
}
int opBinaryRight(string op)(int i) if (op == "<") {
return
On Sunday, 5 April 2015 at 23:15:04 UTC, w0rp wrote:
On Sunday, 5 April 2015 at 23:06:27 UTC, FreeSlave wrote:
I have array of structs sorted by specific field. How can I
perform binary search using this field as a key?
Currently I ended up with this, but it gives error:
struct S
{
int i
On Sunday, 5 April 2015 at 23:06:27 UTC, FreeSlave wrote:
I have array of structs sorted by specific field. How can I
perform binary search using this field as a key?
Currently I ended up with this, but it gives error:
struct S
{
int i;
string s;
}
import std.range;
void main(string
I have array of structs sorted by specific field. How can I
perform binary search using this field as a key?
Currently I ended up with this, but it gives error:
struct S
{
int i;
string s;
}
import std.range;
void main(string [] args)
{
S[] structs = [{1,"hello"}, {2,&q
20 matches
Mail list logo
