🎓 A1Learner
🔍
0 of 55 lessons completed

Zig Searching

Searching is checking values one by one until a target value is found. A linear search starts at the first value and moves in order to the next one.

A present target returns its index

The search checks 3, then 1, then 4. It finds the target 4 at index 2.

const std = @import("std");

fn find(nums: []const i32, target: i32) i32 {
    for (nums, 0..) |value, i| {
        if (value == target) {
            return @intCast(i);
        }
    }
    return -1;
}

pub fn main() !void {
    const out = std.io.getStdOut().writer();
    const nums = [_]i32{ 3, 1, 4, 1, 5 };
    try out.print("{d}\n", .{find(nums[0..5], 4)});
}

A missing target returns -1

The search checks every value and finds no 9. The loop ends and the function returns -1.

const std = @import("std");

fn find(nums: []const i32, target: i32) i32 {
    for (nums, 0..) |value, i| {
        if (value == target) {
            return @intCast(i);
        }
    }
    return -1;
}

pub fn main() !void {
    const out = std.io.getStdOut().writer();
    const nums = [_]i32{ 3, 1, 4, 1, 5 };
    try out.print("{d}\n", .{find(nums[0..5], 9)});
}

The same search finds a byte in a string

A string is bytes, so the same loop searches for one byte. The letter n sits at index 3, and the letter z is missing.

const std = @import("std");

fn findByte(word: []const u8, needle: u8) i32 {
    for (word, 0..) |ch, i| {
        if (ch == needle) {
            return @intCast(i);
        }
    }
    return -1;
}

pub fn main() !void {
    const out = std.io.getStdOut().writer();
    const word: []const u8 = "planet";
    try out.print("{d}\n", .{findByte(word, 'n')});
    try out.print("{d}\n", .{findByte(word, 'z')});
}

Example

const std = @import("std");

fn find(nums: []const i32, target: i32) i32 {
    for (nums, 0..) |value, i| {
        if (value == target) {
            return @intCast(i);
        }
    }
    return -1;
}

pub fn main() !void {
    const out = std.io.getStdOut().writer();
    const scores = [_]i32{ 12, 7, 19, 7, 3 };
    try out.print("{d}\n", .{find(scores[0..5], 19)});
    try out.print("{d}\n", .{find(scores[0..5], 8)});
    try out.print("{d}\n", .{find(scores[0..5], 7)});
}

Key points

  • Target: the target is the value the search is looking for.
  • Linear search: each value is compared with the target in order, from first to last.
  • Found index: a successful search returns the index where the target sits.
  • Missing value: this course returns -1 when the target is not present, because -1 is never a real index.
  • Index type: loop indexes are usize, so @intCast converts a found index to i32 before returning it.

In this example, find searches the scores three times. It returns 2 for 19, -1 for the missing 8, and 1 for 7, because the search stops at the first match.

Note

a search stops as soon as it finds the target, so later values are never checked.

Try it Yourself

Edit the code, then press Run.

Running is simulated

Exercise

What does a linear search return in this course when the target is not in the array?