# Linear Search

## Linear search or sequential search is a method for finding an element within a list. It sequentially checks each element of the list until a match is found or the whole list has been searched. 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
}

}
``````