Linear Search example

🔎 Linear Search (Sequential Search)

What problem are we solving?

Given an array and a target value (the “key”), find the index where the key occurs. If it isn’t present, report that clearly (commonly -1).

When should you use it?

• Arrays or lists that are unsorted (binary search won’t help).

• Small to medium collections where code simplicity matters.

• One-off searches where building an index or sorting is overkill.

How it works (step by step)

1. Start at index 0.

2. Compare the current element to the key.

3. If they match → return the index.

4. Otherwise move to the next element and repeat.

5. If you reach the end with no match → return -1.

Complexity

• Time: O(n) in the worst/average case; O(1) best case (if the key is at index 0).

• Space: O(1) (in-place, no extra memory).

---

Java Implementation

 

package com.vinod.test;

/**
 * LinearSearch (Sequential Search)
 *
 * Problem:
 *   Given an array and a key, return the index of the key if present; otherwise -1.
 *
 * Approach:
 *   Scan from left to right and compare each element with the key.
 *
 * Time Complexity:
 *   Worst/Average: O(n), Best: O(1) if the first element matches.
 *
 * Space Complexity:
 *   O(1)
 *
 * Notes:
 *   - Works on unsorted arrays.
 *   - For sorted arrays, consider Binary Search (O(log n)).
 */
public class LinearSearch {

    public static void main(String[] args) {
        int[] arr = { 1, 3, 5, 7, 9, 12, 16, 18 };

        int key1 = 5;
        int idx1 = indexOf(arr, key1);
        System.out.println("Key " + key1 + " found at index = " + idx1); // expected: 2

        int key2 = 10;
        int idx2 = indexOf(arr, key2);
        System.out.println("Key " + key2 + " found at index = " + idx2); // expected: -1
    }

    /**
     * Returns the zero-based index of {@code key} in {@code arr}, or -1 if not found.
     *
     * @param arr the array to scan (may be unsorted)
     * @param key the value to find
     * @return index of the key if present; otherwise -1
     */
    public static int indexOf(int[] arr, int key) {
        if (arr == null || arr.length == 0) {
            return -1; // handle null/empty safely
        }

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == key) {
                return i; // found
            }
        }
        return -1; // not found
    }
}