www.digitalmars.com         C & C++   DMDScript  

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

reply 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
next sibling parent 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
prev sibling next sibling parent reply 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;
 }




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
Feb 25 2018
parent 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
prev sibling parent 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