Linear Search

Linear Search is a searching algorithm to sequentially traverse a given list or array and check if an element is present in the respective array or list.

The idea is to start traversing the array and compare elements of the array one by one starting from the first element with the given element until a match is found or end of the array or list is reached.

Time Complexity: O(n) as we are traversing all elements in the array in worst case.

Examples:

Input: arr[] = {10, 20, 80, 30, 60, 50, 110, 100, 250}, key: 100

Output: 6

Problem: Given an array arr[] of n elements, write a function to search a given element x in arr[]

Algorithm:

• Start from the leftmost element of arr[] and one by one compare x with each element of arr[]
• If x matches with an element, return the index
• If x doesn't match with any elements and end of the array is reached, return -1.

Solution:

import java.util.List;

/**
 * <p><b>Linear Search</b> is a searching algorithm to sequentially traverse a
 * given list or array and check if an element is present in the
 * respective array or list.</p>
 * <p>The idea is to start traversing the array and compare elements of
 * the array one by one starting from the first element with the given
 * element until a match is found or end of the array or list is reached.</p>
 * <p><b>Time Complexity:</b> O(n)</p>
 * <p><b>Usage:</b></p>
 * {@code
 *  String[] fruits = new String[]{"apple", "mango", "banana", "guava"};
 *  LinearSearch.of(fruits, "guava") // 3
 *  LinearSearch.of(Arrays.asList(fruits), "guava") // 3
 * }
 */
public class LinearSearch {

    /**
     * <b>Flow:</b>
     * <p>1. Start from the left most element of array[] and one by one compare
     *    'x' with each element of array[]</p>
     * <p>2. If x matches with an element return the index</p>
     * <p>3. If x doesn't match with any elements and end of the array is
     *    reached, return -1</p>
     * <p><b>Time Complexity:</b> O(n)</p>
     * @param array type T array
     * @param x element to search
     * @return index of the given element or -1 if not found
     */
    public static <T> int of(T[] array, T x) {
        // start traversing array
        for (int i = 0; i < array.length; i++) {
            if (array[i].equals(x)) { // if successful match found
                return i; // return the index
            }
        }
        return -1; // if element is not found, end of the array
    }

    /**
     * <b>Flow:</b>
     * <p>1. Start from the left most element of list and one by one compare
     *    'x' with each element of list</p>
     * <p>2. If x matches with an element return the index</p>
     * <p>3. If x doesn't match with any elements and end of the list is
     *    reached, return -1</p>
     * <p><b>Time Complexity:</b> O(n)</p>
     * @param list type T list
     * @param x element to search
     * @return index of the given element or -1 if not found
     */
    public static <T> int of(List<T> list, T x) {
        // start traversing list
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i).equals(x)) { // if successful match found
                return i; // return the index
            }
        }
        return -1; // if element is not found, end of the array
    }

}