Searching

containers.IndexOf( xs, v ) returns the index of the first element equal to v, or -1 when there is none; containers.Contains( xs, v ) says whether there is one. Both look at the elements one at a time, from the front. On a sorted array, BinarySearch, LowerBound and UpperBound halve the range at each step instead: about 20 looks for a million elements.

#import "std/containers"

dim scores as containers.Array( of int32 ) = { 70, 85, 90, 85 }

'' IndexOf and Contains walk the array from the front.
dim as int32 wanted = 85, missing = 60
print "first 85 at " & containers.IndexOf( scores, wanted )
print "60 at " & containers.IndexOf( scores, missing )
print "has 60? "; containers.Contains( scores, missing )

'' On a sorted array, a binary search halves the range at each step.
containers.Sort( scores )
print "sorted:"; scores[ 0 ]; scores[ 1 ]; scores[ 2 ]; scores[ 3 ]
dim as int32 top = 90
print "90 at " & containers.BinarySearch( scores, top )
dim r as int32 = containers.BinarySearch( scores, missing )
print "60 gives " & r & ", so it would go at " & -( r + 1 )

'' The bounds bracket every copy of a value.
print "85s from " & containers.LowerBound( scores, wanted ) & _
    " up to " & containers.UpperBound( scores, wanted )

Output

first 85 at 1
60 at -1
has 60? false
sorted: 70 85 85 90
90 at 3
60 gives -1, so it would go at 0
85s from 1 up to 3

A miss in BinarySearch is always negative, and -( r + 1 ) turns it back into the index where the value would go. UpperBound minus LowerBound counts the copies of a value. The sorted searches trust the array to be sorted: on an unsorted one they return some index without complaint. Each has a ...By form taking a comparer, for an array sorted with SortBy.

These are free procedures rather than members of Array because they need = or < on the element type. A member would demand that of every element type an Array is ever declared with; a free procedure asks only where it is called. When you search the same values often, an OrderedSet keeps them sorted for you, and a Set answers Contains without searching.

The value must have the element's type

The searches are generic, and their type is inferred from both arguments, exactly. That is why the example puts 85, 60 and 90 in int32 variables instead of writing them as literals:

#import "std/containers"

dim scores as containers.Array( of int32 ) = { 70, 85, 90 }
print containers.Contains( scores, 90 )   '' 90 is an integer, not an int32

searchliteral.tiko(4,26): error TKO0809: cannot infer the type arguments of 'contains'; write them, as 'contains( of ... )( ... )'

The literal 90 is an integer, and the array holds int32s, so no single element type fits both. Pass a variable of the element type, or name the type as the message suggests: containers.Contains( of int32 )( scores, 90 ).

Activities

1. Search the sorted scores for 85 with BinarySearch, then with UpperBound. Which index does each give, and why?
2. Insert 75 at the position a missed BinarySearch reports, and print the array to check it is still sorted.