# Linear Search Algorithm

• Difficulty Level : Basic
• Last Updated : 24 Aug, 2022

## What is Linear Search

Linear Search is defined as a sequential search algorithm that starts at one end and goes through each element of a list until the desired element is found, otherwise the search continues till the end of the data set. It is the easiest searching algorithm Given an array arr[] of N elements, the task is to write a function to search a given element x in arr[].

Examples:

Input: arr[] = {10, 20, 80, 30, 60, 50,110, 100, 130, 170}, x = 110;
Output: 6
Explanation: Element x is present at index 6

Input: arr[] = {10, 20, 80, 30, 60, 50,110, 100, 130, 170}, x = 175;
Output: -1
Explanation: Element x is not present in arr[].

Follow the below idea to solve the problem:

Iterate from 0 to N-1 and compare the value of every index with x if they match return index

Follow the given steps to solve the problem:

• 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 of the elements, return -1.

Below is the implementation of the above approach:

## C

 `// C code to linearly search x in arr[]. If x``// is present then return its location, otherwise``// return -1` `#include ` `int` `search(``int` `arr[], ``int` `N, ``int` `x)``{``    ``int` `i;``    ``for` `(i = 0; i < N; i++)``        ``if` `(arr[i] == x)``            ``return` `i;``    ``return` `-1;``}` `// Driver's code``int` `main(``void``)``{``    ``int` `arr[] = { 2, 3, 4, 10, 40 };``    ``int` `x = 10;``    ``int` `N = ``sizeof``(arr) / ``sizeof``(arr);` `    ``// Function call``    ``int` `result = search(arr, N, x);``    ``(result == -1)``        ``? ``printf``(``"Element is not present in array"``)``        ``: ``printf``(``"Element is present at index %d"``, result);``    ``return` `0;``}`

## C++

 `// C++ code to linearly search x in arr[]. If x``// is present then return its location, otherwise``// return -1` `#include ``using` `namespace` `std;` `int` `search(``int` `arr[], ``int` `N, ``int` `x)``{``    ``int` `i;``    ``for` `(i = 0; i < N; i++)``        ``if` `(arr[i] == x)``            ``return` `i;``    ``return` `-1;``}` `// Driver's code``int` `main(``void``)``{``    ``int` `arr[] = { 2, 3, 4, 10, 40 };``    ``int` `x = 10;``    ``int` `N = ``sizeof``(arr) / ``sizeof``(arr);` `    ``// Function call``    ``int` `result = search(arr, N, x);``    ``(result == -1)``        ``? cout << ``"Element is not present in array"``        ``: cout << ``"Element is present at index "` `<< result;``    ``return` `0;``}`

## Java

 `// Java code for linearly searching x in arr[]. If x``// is present then return its location, otherwise``// return -1` `class` `GFG {``    ``public` `static` `int` `search(``int` `arr[], ``int` `x)``    ``{``        ``int` `N = arr.length;``        ``for` `(``int` `i = ``0``; i < N; i++) {``            ``if` `(arr[i] == x)``                ``return` `i;``        ``}``        ``return` `-``1``;``    ``}` `    ``// Driver's code``    ``public` `static` `void` `main(String args[])``    ``{``        ``int` `arr[] = { ``2``, ``3``, ``4``, ``10``, ``40` `};``        ``int` `x = ``10``;` `        ``// Function call``        ``int` `result = search(arr, x);``        ``if` `(result == -``1``)``            ``System.out.print(``                ``"Element is not present in array"``);``        ``else``            ``System.out.print(``"Element is present at index "``                             ``+ result);``    ``}``}`

## Python3

 `# Python3 code to linearly search x in arr[].``# If x is present then return its location,``# otherwise return -1`  `def` `search(arr, N, x):` `    ``for` `i ``in` `range``(``0``, N):``        ``if` `(arr[i] ``=``=` `x):``            ``return` `i``    ``return` `-``1`  `# Driver Code``if` `__name__ ``=``=` `"__main__"``:``    ``arr ``=` `[``2``, ``3``, ``4``, ``10``, ``40``]``    ``x ``=` `10``    ``N ``=` `len``(arr)` `    ``# Function call``    ``result ``=` `search(arr, N, x)``    ``if``(result ``=``=` `-``1``):``        ``print``(``"Element is not present in array"``)``    ``else``:``        ``print``(``"Element is present at index"``, result)`

## C#

 `// C# code to linearly search x in arr[]. If x``// is present then return its location, otherwise``// return -1``using` `System;` `class` `GFG {``    ``public` `static` `int` `search(``int``[] arr, ``int` `x)``    ``{``        ``int` `N = arr.Length;``        ``for` `(``int` `i = 0; i < N; i++) {``            ``if` `(arr[i] == x)``                ``return` `i;``        ``}``        ``return` `-1;``    ``}` `    ``// Driver's code``    ``public` `static` `void` `Main()``    ``{``        ``int``[] arr = { 2, 3, 4, 10, 40 };``        ``int` `x = 10;` `        ``// Function call``        ``int` `result = search(arr, x);``        ``if` `(result == -1)``            ``Console.WriteLine(``                ``"Element is not present in array"``);``        ``else``            ``Console.WriteLine(``"Element is present at index "``                              ``+ result);``    ``}``}` `// This code is contributed by DrRoot_`

## PHP

 ``

## Javascript

 ``

Output

`Element is present at index 3`

Time complexity: O(N)
Auxiliary Space: O(1)

## Linear Search Recursive Approach:

Follow the given steps to solve the problem:

• If the size of the array is zero then, return -1, representing that the element is not found. This can also be treated as the base condition of a recursion call.
• Otherwise, check if the element at the current index in the array is equal to the key or not i.e, arr[size – 1] == key
• If equal, then return the index of the found key.

Below is the implementation of the above approach:

## C++14

 `// C++ Recursive Code For Linear Search``#include ``using` `namespace` `std;` `int` `linearsearch(``int` `arr[], ``int` `size, ``int` `key)``{``    ``if` `(size == 0) {``        ``return` `-1;``    ``}``    ``if` `(arr[size - 1] == key) {``        ``// Return the index of found key.``        ``return` `size - 1;``    ``}``    ``else` `{``        ``int` `ans = linearsearch(arr, size - 1, key);``        ``return` `ans;``    ``}``}` `// Driver's Code``int` `main()``{``    ``int` `arr = { 5, 15, 6, 9, 4 };``    ``int` `key = 4;``  ` `      ``// Function call``    ``int` `ans = linearsearch(arr, 5, key);``    ``if` `(ans == -1) {``        ``cout << ``"The element "` `<< key << ``" is not found."``             ``<< endl;``    ``}``    ``else` `{``        ``cout << ``"The element "` `<< key << ``" is found at "``             ``<< ans << ``" index of the given array."` `<< endl;``    ``}``    ``return` `0;``}``// Code contributed by pragatikohli`

## Python3

 `"""Python Program to Implement Linear Search Recursively"""`  `def` `linear_search(arr, key, size):``        ``# If the array is empty we will return -1` `    ``if` `size ``=``=` `0``:``        ``return` `-``1` `    ``# Otherwise if the array consists of only one element and that element is not the one``    ``# we are searching for then it will also return  -1` `    ``elif` `size ``=``=` `1` `and` `arr[``0``] !``=` `key:``        ``return` `-``1` `    ``# ELse , if the element at the size index is same as the element we are searching for``    ``# Then return the size. This will return the index position is 0 index manner.``    ``# i.e if the element is present at 6th position it will return 5.``    ``# To get the exact position in human readble format (counting starts from 1 not 0)``    ``# Then just return size + 1` `    ``elif` `arr[size] ``=``=` `key:``        ``return` `size` `    ``# If none of the conditions are True then in else condition we will call the``    ``# function recursively by decreasing the size by 1 each time.` `    ``else``:``        ``return` `linear_search(arr, key, size``-``1``)` `# Driver's code``if` `__name__ ``=``=` `"__main__"``:``    ``arr ``=` `[``5``, ``15``, ``6``, ``9``, ``4``]``    ``key ``=` `4``    ``size ``=` `len``(arr)``-``1` `    ``# Calling the Function``    ``print``(``"The element "``, key, ``" is found at index: "``,``        ``linear_search(arr, key, size), ``" of given array"``)`  `    ``# Code Contributed By - DwaipayanBandyopadhyay`

## Javascript

 `// JavaScript Recursive Code For Linear Search` `let linearsearch = (arr, size, key) => {``  ``if` `(size == 0) {``    ``return` `-1;``  ``}``  ``if` `(arr[size - 1] == key)``  ``{``  ` `    ``// Return the index of found key.``    ``return` `size - 1;``  ``}``  ``else``  ``{``    ``let ans = linearsearch(arr, size - 1, key);``    ``return` `ans;``  ``}``};` `// Driver Code``let main = () => {``  ``let arr = [5, 15, 6, 9, 4];``  ``let key = 4;``  ``let ans = linearsearch(arr, 5, key);``  ``if` `(ans == -1) {``    ``console.log(`The element \${key} is not found.`);``  ``} ``else` `{``    ``console.log(``      ```The element \${key} is found at \${ans} index of the given array.```    ``);``  ``}``  ``return` `0;``};` `main();` `// This code is contributed by Aman Singla...`

Output

`The element 4 is found at 4 index of the given array.`

Time Complexity: O(N)
Auxiliary Space: O(1)

My Personal Notes arrow_drop_up