Start learning free

LESSON 146 OF 338 · LOOPING OVER ARRAY INDICES

Linear Search in Go: O(n) Index Lookup in a Slice

Practice Read the full explanation

Given an array of integers nums, return the index of a given value.

If the value doesn't exist, return -1.

Example 1:

Input: nums = [1, 2, 4, 5], value = 4
Output: 2
Explanation: nums[2] is 4

Note:

Your algorithm should run in O(n) time and use O(1) space.


Hints:

We should try out each element in nums until we find one equal to value and return its index. How can we achieve this?

With a for loop, of course! We can use a variable num to iterate through the elements and an if statement to check if num == value: 
for each num in nums:
	if num == value:
    # Solution found! But...

This is how we look for value in nums, but there's a problem. The problem asks us to return the index of that element, and by iterating like this we only know the value of the current element, not its index. How can we fix this?

We should use another method of iterating through an array: by indices! Let's use an index variable i to go through every index between 0 and nums.length - 1: 
for i : 0 -> nums.length - 1:
	# index is i, value is nums[i]
  	if nums[i] == value:
    		return i
What if we don't have any element equal to value? Where should we return -1? 

for i : 0 -> nums.length - 1:
	# index is i, value is nums[i]
  	if nums[i] == value:
    		return i

# Here:
return -1
If we reach the line with the comment, this means the for loop terminated naturally without returning any index. If we have had returned an index, we wouldn't even be executing this line of code as the program would have finished.

We have a for loop that performs exactly n iterations (where n is the length of nums), thus the Time Complexity is O(n).
The only extra space we use is the iterator variable i inside the loop, thus the Extra Space used is O(1).

Video Solution:

STEP 1 OF 3
    Ctrl + Enter to check

    GO · LOOPING OVER ARRAY INDICES

    Linear Search in Go, explained

    Problem overview

    The function find receives a slice of integers, nums, and an integer value. It returns the index where value sits, or -1 if the value isn't in the slice. For nums = [1, 2, 4, 5] and value = 4 the answer is 2, because nums[2] is 4.

    The task sets a budget of O(n) time and O(1) extra space, which a single pass over the slice meets.

    Approach

    Linear search checks the elements one by one, from the first, until one equals value. At that moment the position is known and the function can return it. If the loop ends without a match, the value is not present.

    The question asks for a position, not for the value itself. A range loop that takes the element, as in for _, num := range nums, tells you the value of each element but loses its position. Taking the index instead solves this: the index is available in the loop, and the element is just nums[i].

    Step by step

    1. Loop with range, keeping only the index. When range over a slice is given a single variable, that variable is the index, not the element. for i := range nums therefore walks through 0, 1, 2, ... up to the last index.
    2. Compare and return. Inside the loop, if nums[i] == value, return i immediately. Returning ends the function, so the search stops at the first match. If the value appears more than once, the caller gets its first index.
    3. Return -1 after the loop. The line below the loop runs only if the loop finished without returning. That means no element matched. The value -1 can never be a real index, so the caller can tell "not found" from any valid answer.

    The solution in Go

    func find(nums []int, value int) int {
    for i := range nums {
        if nums[i] == value {
            return i
        }
    }
    return -1
}

    The Go details worth knowing:

    • One variable versus two. for i := range nums gives the index. for _, num := range nums gives the element and discards the index. for i, num := range nums gives both, and then both must be used.
    • Equivalent counting loop. for i := 0; i < len(nums); i++ does the same job. The range form cannot run past the end by accident.
    • The function needs a final return. Go reports "missing return" if a function with a result can reach its closing brace without returning. The loop alone doesn't satisfy that rule, since the compiler can't know that it will return, so return -1 is required.
    • Comparing with ==. For int values == compares the numbers. Comparing a slice with another slice using == is not allowed, but nothing like that happens here.

    Complexity

    Time: O(n). In the worst case, the value is last or missing, and the loop performs n comparisons, where n is the length of the slice. When the value is first, it takes one. The bound is for the worst case.

    Space: O(1). The only extra memory is the loop index.

    Linear search works on any slice, sorted or not. If the slice is sorted, binary search can find the value in O(log n), but this lesson doesn't assume sorted data.

    Edge cases and common mistakes

    • Value not present. [1, 2, 4, 5] with 3 returns -1.
    • Duplicates. [7, 7] with 7 returns 0, the first index.
    • Empty or nil slice. The loop does not run and the function returns -1.
    • Returning -1 inside the loop. An else { return -1 } on the if would give up after the first element that doesn't match. The -1 belongs after the loop.
    • Returning the element. return nums[i] would give back the value, which the caller already has.

    Testing

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