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
