# How to Search an Element in an Array

Simplest method for searching an element in an array is **sequential search** or **linear search**. It is performed in a linear way i.e. start from the beginning of the array and continue till we find the item or reach the end of the list. The item to be searched is compared with each element of the array one by one starting from the first element.

For example consider the following array:

$$

\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|}

\hline

96 & 25 & 28 & 35 & 45 & 75 & 62 & 71 & 81 & 15 & 11 & 4 \\

\hline

\end{array}

$$

suppose we want to search for value \(71\) in this array. This value is compared with \(arr[0]\), \(arr[1]\), \(arr[2]\), …, \(arr[7]\). Since the value is found at index \(7\), the search is successful. The steps of Linear Search are shown below:

Now suppose we have to find the value 56 in the above array. This value is compared with \(arr[0]\), \(arr[1]\), …, \(arr[11]\)**. **The value was not found even after examining all the elements of the array so the search is unsuccessful.

**Implementation of Linear Search**

C implementation of Linear Search is given below:

#include<stdio.h> #include<stdlib.h> #define MAX 50 int linearSearch(int arr[], int size, int item){ int i = 0; while(i < size && item != arr[i]){ i++; } if(i < size){ return i; } else{ return -1; } } // Driver Function int main(void){ int n, arr[MAX], item; printf("Enter the number of elements: "); scanf("%d", &n); if(n >= MAX){ printf("Error: Number of element is larger than allocated space."); exit(0); } else{ printf("Enter the elements: "); for(int i = 0; i < n; i++){ scanf("%d", &arr[i]); } } printf("Enter the element to be searched: "); scanf("%d",&item); int index = linearSearch(arr, n, item); if(index == -1){ printf("%d not found in the array. \n", item); } else{ printf("%d found at position %d. \n", item, index); } return 0; }

The function
linearSearch() returns the location of the element if found or **-1** otherwise. The while loop can terminate in two cases:

- When value of
**i**becomes equal to**n**. This is the case when whole array has been scanned and item is not found in the array. - When the value of the item is found in the array, i.e., item == arr[i]

**Time complexity of Linear Search**

Since in the worst case, we must traverse till the end of the array, hence in worst case time complexity is \(\mathcal O(n)\).

If the array is sorted time complexity will be reduced from \(\mathcal O(n)\) to \(\mathcal O(\log n)\). In the next post we discuss about Binary Search.

This article is contributed by Ram Kripal. If you like eLgo Academy and would like to contribute, you can mail your article to admin@elgoacademy.org. See your article appearing on the eLgo Academy page and help other Geeks. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.