Start learning free

LESSON 130 OF 338 · LOOPS & CONDITIONALS

Array Contains in Go: Linear Search with range

Practice Read the full explanation

Given an array of integers nums and another integer value, check if value occurs in nums.

If the value occurs in nums, return true; otherwise return false.


Examples:

contains([]int{1, 2, 4, 5}, 4) -> true

contains([]int{-1, 2, -4, 0, 10}, 7) -> false

Note:

Do not use builtin functions such as slices.Contains(), it would defy the purpose of the challenge. Write the whole code yourself.

STEP 1 OF 3
    Ctrl + Enter to check

    GO · LOOPS & CONDITIONALS

    Array Contains in Go, explained

    Problem overview

    The function contains receives a slice of integers, nums, and an integer value. It returns true if value appears anywhere in nums and false otherwise. The lesson asks you to write the search yourself rather than call a library function such as slices.Contains.

    For contains([]int{1, 2, 4, 5}, 4) the answer is true, because 4 is the third element. For contains([]int{-1, 2, -4, 0, 10}, 7) the answer is false: none of the five elements equals 7.

    Approach: look at every element until one matches

    An unsorted slice gives no hint about where a value might be, so the only way to be sure it is missing is to look at every element. This is a linear search. Walk through the slice from the start and compare each element with value. The first time they are equal, the answer is true, and there is no reason to keep looking. If the walk ends without a match, the answer is false.

    The order of the two returns matters. true can be decided in the middle of the loop, but false can only be decided after the loop has looked at everything. That is why return false sits after the loop and never inside it.

    Step by step

    1. Loop over the slice with for ... range, naming the element num. The loop gives each element in turn, from the first to the last.
    2. Compare inside the loop. If num == value, return true immediately. Returning ends the whole function, so the remaining elements are never examined.
    3. Return false after the loop. This line is reached only when no element matched, so no else is needed.

    The solution in Go

    func contains(nums []int, value int) bool {
    for _, num := range nums {
        if num == value {
            return true
        }
    }
    return false
}

    The Go details that matter here:

    • range yields an index and a value. Only the value is needed, so the index is assigned to the blank identifier _. Go treats an unused variable as a compile error, so naming it and ignoring it would not compile.
    • num is a copy. Each pass copies the element into num. That is harmless for a read-only search.
    • == works directly on int. No special method is needed for numbers.
    • Every path returns. A function declared to return bool must end in a return statement. The final return false covers the case where the loop finishes, and it also covers an empty or nil slice, where the loop body never runs.

    Complexity

    Time: O(n). In the worst case, the value is last or missing, and the loop makes one comparison per element. In the best case the first element matches and the loop stops at once.

    Space: O(1). The function uses only the loop variable. It does not copy the slice, since a slice passed to a function shares the same underlying elements.

    Edge cases and common mistakes

    • Empty slice. contains([]int{}, 5) is false, and so is contains(nil, 5). Ranging over either runs the body zero times.
    • Returning false inside the loop. Writing else { return false } after the comparison would stop at the first element that doesn't match. contains([]int{1, 2, 4, 5}, 4) would wrongly give false, because 1 is not 4.
    • Negative numbers and zero. They compare like any other integer. contains([]int{-1, 2, -4, 0, 10}, 0) is true.
    • Duplicates. The function stops at the first match, so repeated values cost nothing extra.
    • Counting instead of stopping. A counter plus a final check also works but keeps scanning after the answer is known. The early return is shorter and faster.

    Testing

    • contains([]int{1, 2, 4, 5}, 4) gives true.
    • contains([]int{-1, 2, -4, 0, 10}, 7) gives false.
    • contains([]int{}, 1) gives false.
    • contains([]int{3}, 3) gives true.
    Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free