Re: Searching string for character in binary search
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.
Re: Searching string for character in binary search
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's good to know that it does work and uses a
binary search!
You can see that it only does a few comparisons with something like:
https://run.dlang.io/is/lax6YP
Also, strings are not doing what you think:
"abcd".find('c'); // OK, linear search
"abcd".assumeSorted.find('c'); // Error
"abcd".assumeSorted.find("c"); // OK, but does NOT do a binary search!
[1,2,3,4].assumeSorted.find([3]); // OK, but also does not do a binary
search!
My knee-jerk reaction is to blame auto-decoding ;) But maybe it's just a
bug.
If you want to guarantee a binary search (i.e. compiler error when it
cannot do it), you need to use SortedRange.lowerBound.
-Steve
Re: Searching string for character in binary search
On Sunday, 25 February 2018 at 21:18:55 UTC, Joel wrote:
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 passed!");
}
bool binarySearch(T)(T[] arr, T n) {
while(arr.length) {
auto i = arr.length/2;
if (arr[i] == n)
return true;
else
if (arr[i] > n)
arr = arr[i + 1 .. $];
else
arr = arr[0 .. i];
}
return false;
}
Your cases are wrong:
---
if (arr[i] > n) // 'n' > 'j'
// 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
Re: Searching string for character in binary search
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.
Searching string for character in binary search
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 passed!");
}
bool binarySearch(T)(T[] arr, T n) {
while(arr.length) {
auto i = arr.length/2;
if (arr[i] == n)
return true;
else
if (arr[i] > n)
arr = arr[i + 1 .. $];
else
arr = arr[0 .. i];
}
return false;
}
