Best way to check for an element in an array?

[Ali Çehreli via Digitalmars-d-learn]

On 04/21/2014 09:22 PM, Taylor Hillegeist wrote:

 > Question though? why doesn't canFind() work on statically
 > allocated arrays?

That's an issue all of face from time to time. (Happened to me again 
last week. :) )

The reason is, algorithms like canFind work with input ranges and 
fixed-length arrays are not input ranges because they cannot support 
popFront(), which would reduce their length.

The solution is to use a full slice of the array by appending [] to it:

      if (stuff[].canFind(2)) {    // <-- note []

It works because now canFind() operates on a temporary slice (aka 
dynamic array).

Getting back to your original question, std.algorithm.find and canFind() 
are O(N) algorithms, which is too slow if you already have a sorted range.

When you indeed have a sorted range, you can pass it through 
assumeSorted() to create a SortedRange object so that you can take 
advantage of O(log N) algorithms like trisect() and friends (one of 
those friends is contains()):

import std.range;

void main()
{
     auto arr = [ 1, 2, 3, 3, 4, 5 ];
     auto result = arr.assumeSorted.trisect(3);

     assert(result[0].equal([ 1, 2 ]));
     assert(result[1].equal([ 3, 3 ]));
     assert(result[2].equal([ 4, 5 ]));
}

The search in that program is O(log N).

Ali