Start learning free

LESSON 151 OF 415 · LOOPING OVER ARRAY INDICES

Linear Search in Swift: Finding an Index in O(n)

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 is equal to value. If it is, we have found the solution! 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.count - 1.
For each index i, the index is i and the value is the element of nums at that index. If that element is equal to value, we return i.
What if we don't have any element equal to value? Where should we return -1?

After the loop, outside of it, we return -1.
If we reach that line, this means the for loop terminated naturally without returning any index. If we 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

    SWIFT · LOOPING OVER ARRAY INDICES

    Linear Search in Swift, explained

    Problem overview

    The method find receives an array of integers, nums, and an integer value. It returns the index of value in the array, or -1 when the value isn't there. For nums = [1, 2, 4, 5] and value = 4 the answer is 2, because nums[2] is 4.

    The lesson asks for O(n) time and O(1) extra space.

    Approach: check every position in order

    With no information about the array, the only way to be sure a value is missing is to look at every element. So the plan is to go from the first position to the last, compare each element with value, and stop as soon as one matches. If the end is reached with no match, the value isn't present.

    The answer is a position, not a value, so the loop must carry an index. A loop such as for num in nums hands you the values only, and you would have to count positions by hand. Looping over the indices 0..<nums.count gives you both: the index i and the element nums[i].

    Step by step

    1. Loop over every index. for i in 0..<nums.count runs from 0 to the last valid index.
    2. Compare and return early. If nums[i] == value, return i at once. This ends the function at the first match, so when the value occurs several times, the lowest index is returned.
    3. Return -1 after the loop. The line is reached only when no comparison matched. A negative number can't be an index, so it can't be confused with a real result.

    The solution in Swift

    class Solution {
    func find(_ nums: [Int], _ value: Int) -> Int {
        for i in 0..<nums.count {
            if nums[i] == value {
                return i
            }
        }
        return -1
    }
}

    Swift details worth knowing:

    • Half-open range. 0..<nums.count excludes its upper bound, so the largest index used is nums.count - 1. For an empty array the range is empty and the body never runs.
    • Return from inside a loop. A return leaves the whole method, not just the loop. That is what makes the search stop early.
    • The final return -1 is required. The compiler insists that every path returns an Int. Without that line, the method reports "missing return in instance method expected to return 'Int'".
    • Optionals are the alternative. Swift code often returns Int? for "maybe a position", with nil for not found. This lesson uses -1 instead, as the return type is a plain Int.
    • Labels. Both parameters use _, so a call looks like find([1, 2, 4, 5], 4).

    Complexity

    Time: O(n) for an array of n elements. In the worst case, when the value is last or absent, the loop does n comparisons. A match near the front finishes sooner, but the bound covers the worst case.

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

    Edge cases and common mistakes

    • Not found. [1, 2, 4, 5] with value = 9 returns -1.
    • Empty array. The loop doesn't run and the result is -1.
    • Duplicates. [3, 3] with value = 3 returns 0, the first index.
    • Returning -1 inside the loop. If the else side of the comparison returns -1, the function gives up after the first element.
    • Returning the value instead of the index. return nums[i] returns value itself.
    • Looping to nums.count inclusive. 0...nums.count would read nums[nums.count] on a miss and crash.

    Testing

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