Linear Search Algorithm

Linear Search Algorithm.

Introduction:

In this tutorial, we will be learning what is Linear Search Algorihtm and how it is used with an Algorihtm code. So, I'm assuming that you have a good knowledge of Arrays, Loops. Because we will be using Loops and Arrays during this process.

Linear Search: Linear as name suggest which is one by one linearly in one direction. So, Linear Search is used for searching an element in an array linearly one by one. In Linear Search we iterate over each element one by one and when an element is found we return its index. If we have not found element in array we can return -1.

Example:

Input: arr[] = { 2, 3, 4, 6, 10 }, x = 3
Output: 1
(because index of 3 is 1)
Input: arr[] = { 2, 3, 4, 6, 10 }, x = 15
Output: -1
(because 15 is not found in array)

Now Let's have a quick look on steps/algorithm of LINEAR SEARCH.

Algorithm:

Start a loop starting from index i=0 which goes until i < n (Here n is size of Array).
If arr[i] matches with element (which is to be searched).
- return i.
Otherwise, return -1.
At Last, Loop ends.

JAVA
PYTHON

public class LinearSearch {
    public static void main(String[] args) {
        int arr[] = { 2, 3, 4, 6, 10 };
        int x = 6;
        
        // returned value from search() method will be stored in result.
        int result = search(arr, x);
        if (result == -1) {
            System.out.println("Element is not present in Array");
        } else {
            System.out.println("Element is present in Array at index: " + result);
        }
    }

    public static int search(int arr[], int x) {
        // time complexity is O(n)
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            if (arr[i] == x) {
                return i;
            }
        }
        // if element is not found in array return -1.
        return -1;
    }
}

def LinearSearch(arr, x):
    # time complexity is O(n)
    n = len(arr)
    for i in range (0, n):
        if arr[i] == x:
            return i
    # if element is not found in array return
    return -1

if __name__ == '__main__':
    arr = [2, 3, 4, 6, 8]
    x = 6
    result = LinearSearch(arr, x)
    if result == -1:
        print("Element is not present in Array")
    else:
        print("Element is present in Array at index: " ,result)

Output:

Element is present in Array at index: 3

Complexity Analysis:

Time Complexity: O(n), In worst case time complexity of this algorithm can go upto O(n) as we have to traverse whole array.
Space Complexity: O(1), we have not used any extra space.

Linear Search Algorithm