LESSON 145 OF 347 · LOOPING OVER ARRAY INDICES

Linear Search in C#: Find the Index of a Value in O(n)

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

Guided

Ctrl + Enter to check

Linear Search in C#, explained

Problem overview

Find(int[] nums, int value) returns the index at which value appears in nums, or -1 when it isn't there. For nums = [1, 2, 4, 5] and value = 4, the answer is 2, because nums[2] is 4.

The statement asks for O(n) time and O(1) extra space, which fits the most direct approach: look at the elements one by one from the start.

Approach: check each position until you find it

This is linear search. Start at index 0, compare the element with value, and move on to the next index if they differ. The moment you find a match, you know the answer and can stop. If you get to the end of the array without a match, the value isn't there.

A plain foreach would give you each value but not its position. Since the answer is an index, the loop has to run over the indices themselves, so that i is the position and nums[i] is the value there.

Linear search works on any array, sorted or not. When an array is sorted, you can do better with binary search, but that needs the ordering. Here, nothing is assumed.

Step by step

Loop over every index. Write for (int i = 0; i < nums.Length; i++). The condition uses < because the last valid index is Length - 1.
Compare and return immediately. Inside the loop, if (nums[i] == value) detects the match, and return i; leaves the method with the position. Returning right away also means that if the value occurs several times, you get the first index.
Return -1 after the loop. Reaching this line means no return ran inside the loop, so no element matched. The value -1 can't be a valid index, so the caller can't confuse it with a real position.

The solution in C#

class Solution {
    public int Find(int[] nums, int value) {
        for (int i = 0; i < nums.Length;i++) {
            if (nums[i] == value) {
                return i;
            }
        }
        return -1;
    }
}

C# details worth noting:

Every path returns a value. The compiler requires that the method returns an int on every route. Without the final return -1;, the code would not compile, because the loop might finish without returning.
Length is a property. Write nums.Length, with a capital L and no parentheses.
== compares numbers by value. For int it does exactly what you expect. (For other types, such as strings, == also compares contents in C#, but this lesson only uses integers.)
A built-in exists. Array.IndexOf(nums, value) does the same job and also returns -1 when the value is missing. Writing the loop yourself shows what it does inside.

Complexity

Time: O(n). In the worst case, the value is last or missing, and the loop makes n comparisons, where n is nums.Length. If the value is first, the loop stops after one comparison, but the bound for the worst case is what counts.

Space: O(1). The only extra variable is the index i.

Edge cases and common mistakes

The value is missing. The loop ends without a return, and the method returns -1. For [1, 2, 4, 5] and value 3, the result is -1.
An empty array. The loop doesn't run, so the answer is -1.
Duplicates. [4, 4] with value 4 returns 0, the first index, because the method returns at the first match.
Putting return -1 inside the loop. The method would give up after the first element that doesn't match. The "not found" answer is only certain after every element has been checked, so it goes below the loop.
Returning the value instead of the index. return nums[i]; compiles but answers a different question. For the example it would return 4 instead of 2.
Using <= in the loop condition. The last pass would read nums[nums.Length], and the program would throw an IndexOutOfRangeException when the value isn't found earlier.
Using = instead of ==. An assignment inside the if isn't a bool, so C# rejects it at compile time.

Testing

[1, 2, 4, 5] with value 4 gives 2.
[1, 2, 4, 5] with value 3 gives -1.
[4, 4] with value 4 gives 0.
[7] with value 7 gives 0.
[] with value 1 gives -1.

Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free