## digitalmars.D.learn - Searching string for character in binary search

• Joel (22/22) Feb 25 2018 The number tests work, but not the string one.
• ag0aep6g (3/5) Feb 25 2018 When `arr[i]` is greater than `n`, then the values in `arr[i + 1 .. \$]`
• Seb (13/35) Feb 25 2018 Your cases are wrong:
• Steven Schveighoffer (17/25) Feb 25 2018 canFind (and find) works even on non-sorted ranges, so it's not the
• Joel (3/4) Feb 25 2018 Thanks guys. I worked it out, I thought my search code was right,
Joel <joelcnz gmail.com> writes:
```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;
}
```
Feb 25 2018
ag0aep6g <anonymous example.com> writes:
```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.
```
Feb 25 2018
Seb <seb wilzba.ch> writes:
```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;
}

---
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
```
Feb 25 2018
Steven Schveighoffer <schveiguy yahoo.com> writes:
```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
```
Feb 25 2018
Joel <joelcnz gmail.com> writes:
```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.
```
Feb 25 2018