Search

A linear search looks at the elements one by one, from the front, until it finds what it wants. It works on any slice, sorted or not, and it takes time in proportion to the length: twice the elements, twice the looking. The interesting part is not the looking but the answer, because the value you want may not be there at all.

"Where is it?" may have no answer

IndexOf returns the position of the first element equal to the value. No position could honestly say "nowhere": 0 is a real position, and a made-up one such as the length is easy to use by mistake. So the answer is an optional index, uint?, and it is none when nothing matched — the Optional idea from Part 8.

Report takes the answer apart with a presence match before it uses it:

func Report(rolls: int[..], value: int) {
    match IndexOf(rolls, value) {
        at? => PrintLine("{} first appears at {}", value, at),
        none => PrintLine("{} was never rolled", value)
    }
}

Inside the at? arm, at is a plain uint you can print or index with. Outside the match there is only the uint?, and the compiler will not let you treat it as a position until you have looked.

let rolls: int[8] = [4, 2, 6, 6, 1, 3, 6, 5];

Report(rolls, 1);
Report(rolls, 6);
Report(rolls, 7);

1 appears once, at index 4. 6 appears three times; IndexOf reports the earliest, index 2. 7 is not there, so the none arm runs.

Three questions, three functions

LastIndexOf searches from the back, which matters only when the value appears more than once: for 6 it reports index 6, not 2. Contains answers the plainer question with a plain bool, so there is nothing to unwrap:

PrintLine("contains 5  {}", Contains(rolls, 5));
PrintLine("contains 0  {}", Contains(rolls, 0));

The Algorithms package has more in the same family: Count says how many elements equal a value, and IndexWhere finds the first element a function of yours accepts, for searches that are not about equality.

A stand-in with ??

When a missing value has an obvious stand-in, ?? supplies it:

let at = IndexOf(rolls, 7) ?? rolls.length;
PrintLine("7 at {} of {}", at, rolls.length);

at is now a plain uint. The length works as "past the end", but notice what has happened: the type no longer says "maybe absent", so the code that reads at has to remember that 8 means "not found". Use the stand-in when that meaning is obvious and local; keep the uint? when it travels further.

Positions are relative to the slice

A search of part of an array reports positions within that part:

let tail = rolls[4..];
PrintLine("6 in the tail at {}", IndexOf(tail, 6) ?? tail.length);

tail starts at index 4 of rolls, so its own index 2 is index 6 of the array. IndexOf only ever sees the slice it is given, and has no idea where that slice came from.

The program

The whole lesson is one package in the Examples repository. Its comments explain every step.

// A linear search looks at the elements one by one, from the front, until it finds what it wants.
// It works on any slice, sorted or not, and takes time in proportion to the length.
//
// `IndexOf` answers "where is it?". The value might not be there at all, and no index could
// honestly say so: 0 is a real position, and a made-up one such as the length is easy to use by
// mistake. So the answer is an optional index, `uint?`, which is `none` when nothing matched, and
// the program has to look before it can use the position.
//
// `Contains` answers the plainer question "is it there?" with a `bool`. `LastIndexOf` searches
// from the back, which matters only when the value appears more than once.
import Algorithms::{ Contains, IndexOf, LastIndexOf };
import Io::PrintLine;

func Report(rolls: int[..], value: int) {
    match IndexOf(rolls, value) {
        at? => PrintLine("{} first appears at {}", value, at),
        none => PrintLine("{} was never rolled", value)
    }
}

func Main() -> int {
    let rolls: int[8] = [4, 2, 6, 6, 1, 3, 6, 5];

    // Present once, present three times, and absent. With several matches, `IndexOf` reports the
    // earliest.
    Report(rolls, 1);
    Report(rolls, 6);
    Report(rolls, 7);

    match LastIndexOf(rolls, 6) {
        at? => PrintLine("6 last appears at {}", at),
        none => PrintLine("6 was never rolled")
    }

    PrintLine("contains 5  {}", Contains(rolls, 5));
    PrintLine("contains 0  {}", Contains(rolls, 0));

    // When a missing value has an obvious stand-in, `??` supplies it. Here the length works as
    // "past the end", but now the code has to remember that it means "not found".
    let at = IndexOf(rolls, 7) ?? rolls.length;
    PrintLine("7 at {} of {}", at, rolls.length);

    // A search of part of the array reports positions within that part, not within the array.
    let tail = rolls[4..];
    PrintLine("6 in the tail at {}", IndexOf(tail, 6) ?? tail.length);
    return 0;
}

Besides Io, its Rux.toml lists Algorithms under [Dependencies].

Run it

cd Examples/Algorithms/Search
rux run

1 first appears at 4
6 first appears at 2
7 was never rolled
6 last appears at 6
contains 5  true
contains 0  false
7 at 8 of 8
6 in the tail at 2

Common mistakes

Try it yourself

1. Use Count(rolls, 6) to print how many sixes were rolled. Remember to add Count to the import.
2. Write func IsHigh(value: int) -> bool that accepts rolls above 4, and print the result of IndexWhere(rolls, IsHigh) ?? rolls.length.
3. Change Report to also print the last position, using LastIndexOf, but only when it differs from the first.
4. Search a string. Declare let text: char8[..] = "rux-lang"; and let dash: char8 = '-';, then print IndexOf(text, dash) ?? text.length. Then try IndexOf(text, '-') and work out why it is rejected: a character literal with no typed partner is a char, not a char8.

Learn more

• Slices in the Rux Reference
• Presence and Coalesce — the two ways to use an optional answer
• Binary search — a much faster search, when the data is sorted
• Min and max — another search whose answer may be none