☕ DSA Java Articles

Topics › Arrays › Easy

Linear Search

Easy TUF ID 41 A2Z

Java source ↗ Edit this article ↗

Problem

You are given an array of integers nums and a value target. Return the index of the first occurrence of target in nums, or -1 if it does not occur. The array is not sorted, so there is no structure to exploit: every element is a candidate until it has been looked at.

Constraints: 0 ≤ n ≤ 10^5, values and target fit in a 32-bit signed integer.

Example 1

nums = [6, 7, 8, 4, 1], target = 4
answer = 3              // nums[3] == 4

Example 2

nums = [6, 7, 8, 4, 1], target = 9
answer = -1             // 9 is not in the array

Example 3

nums = [2, 3, 2, 3], target = 3
answer = 1              // the first 3 is at index 1; index 3 also holds a 3 but is not the first

Linear search is the baseline every other search is measured against. It also hides a few genuinely useful ideas: a clean loop-with-early-return, the recursive formulation that later becomes backtracking, and the sentinel trick that removes a comparison from the inner loop.

Approach 1: Iterative scan

Intuition. Look at each element in turn. The moment one equals target, its index is the answer, and because we scan from the left it is automatically the first occurrence. If the loop runs off the end, the value is absent.

Algorithm.

  1. For i from 0 to n - 1: if nums[i] == target, return i.
  2. Return -1.
static int iterative(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == target) return i;
    }
    return -1;
}

Complexity. Time O(n) in the worst case (target absent or last); O(1) in the best case. Space O(1).

Why can this not be improved for unsorted input? Any algorithm that skips an element could be fooled by placing the target exactly there, so in the worst case every element must be examined. n comparisons is a lower bound as well as an upper bound. The only way to search faster is to know something about the data, such as sortedness, which is what Search X in sorted array exploits with binary search.

Approach 2: Recursive scan

Intuition. “Search nums[i..n-1] for target” can be defined in terms of a smaller problem: if i is past the end, the answer is -1; if nums[i] is the target, the answer is i; otherwise the answer is whatever searching nums[i+1..n-1] gives. Each call handles one element and delegates the rest.

Algorithm.

  1. Entry point: call the helper with i = 0.
  2. Helper: if i == n, return -1. If nums[i] == target, return i. Otherwise return the helper’s result for i + 1.
static int recursive(int[] nums, int target) {
    return recursive(nums, target, 0);
}

static int recursive(int[] nums, int target, int i) {
    if (i == nums.length) return -1;             // ran off the end: not found
    if (nums[i] == target) return i;
    return recursive(nums, target, i + 1);
}

Complexity. Time O(n). Space O(n) for the call stack, one frame per element examined. Java does not perform tail-call elimination, so with n = 10^5 this will throw StackOverflowError on a default stack. The recursion is here to show the shape, not to use in production.

The shape matters: “check this position, otherwise recurse on the rest” is the skeleton of every recursive array traversal, and adding a second recursive call (take this element or skip it) turns it into subset enumeration.

Intuition. The loop in Approach 1 does two comparisons per element: i < nums.length and nums[i] == target. The bounds check exists only because the target might be absent. Make it present: overwrite the last element with target. Now the scan is guaranteed to stop, so the loop can be while (nums[i] != target) i++ with no bounds check at all. Afterwards restore the last element and decide what the stopping index means: if the scan stopped before the last slot it found a real match; if it stopped at the last slot, that is a real match only if the original last element was the target.

Algorithm.

  1. If n == 0, return -1.
  2. Save last = nums[n - 1] and set nums[n - 1] = target.
  3. Scan i from 0 while nums[i] != target.
  4. Restore nums[n - 1] = last.
  5. If i < n - 1, or last == target, return i; otherwise return -1.
static int sentinel(int[] nums, int target) {
    int n = nums.length;
    if (n == 0) return -1;
    int last = nums[n - 1];
    nums[n - 1] = target;                        // the scan is now guaranteed to stop
    int i = 0;
    while (nums[i] != target) i++;
    nums[n - 1] = last;                          // undo the temporary write
    if (i < n - 1 || last == target) return i;   // a real match, either before the sentinel or at it
    return -1;
}

Dry run on nums = [6, 7, 8, 4, 1], target = 9: last = 1, the array temporarily becomes [6, 7, 8, 4, 9]. The scan passes 6, 7, 8, 4 and stops at i = 4. Restore nums[4] = 1. Since i == n - 1 and last != target, return -1. With target = 1 instead: the array is unchanged by the write, the scan stops at i = 4, and last == target, so return 4.

Complexity. Time O(n), with roughly half the comparisons of the plain loop. Space O(1).

Modern JIT compilers often make this optimisation irrelevant, and the method temporarily mutates its input, which is a real downside if another thread is reading the array. Treat it as a classic worth recognising rather than a default to reach for. The tests confirm that the array is bit-for-bit identical after the call.

Variant: all occurrences

When the question is “every index where target appears”, the early return disappears and the matches are collected:

static List<Integer> allOccurrences(int[] nums, int target) {
    List<Integer> result = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == target) result.add(i);
    }
    return result;
}

Time O(n), space O(k) for k matches. The first element of this list is what the three methods above return, and an empty list corresponds to -1.

Edge cases and pitfalls