Linear search is a sequential searching algorithm where we start from one end and check every element of the list until the desired element is found. It is the simplest searching algorithm.
How Linear Search Works?
The following steps are followed to search for an element k = 1 in the list below.
- Start from the first element, compare k with each element x.
Compare with each element - If
x == k, return the index.
Element found - Else, return not found.
Linear Search Algorithm
LinearSearch(array, key)
for each item in the array
if item == value
return its index
Python, Java and C/C++ Examples
# Linear Search in Python
def linearSearch(array, n, x):
# Going through array sequencially
for i in range(0, n):
if (array[i] == x):
return i
return -1
array = [2, 4, 0, 1, 9]
x = 1
n = len(array)
result = linearSearch(array, n, x)
if(result == -1):
print("Element not found")
else:
print("Element found at index: ", result)
// Linear Search in Java
class LinearSearch {
public static int linearSearch(int array[], int x) {
int n = array.length;
// Going through array sequencially
for (int i = 0; i < n; i++) {
if (array[i] == x)
return i;
}
return -1;
}
public static void main(String args[]) {
int array[] = { 2, 4, 0, 1, 9 };
int x = 1;
int result = linearSearch(array, x);
if (result == -1)
System.out.print("Element not found");
else
System.out.print("Element found at index: " + result);
}
}
// Linear Search in C
#include <stdio.h>
int search(int array[], int n, int x) {
// Going through array sequencially
for (int i = 0; i < n; i++)
if (array[i] == x)
return i;
return -1;
}
int main() {
int array[] = {2, 4, 0, 1, 9};
int x = 1;
int n = sizeof(array) / sizeof(array[0]);
int result = search(array, n, x);
(result == -1) ? printf("Element not found") : printf("Element found at index: %d", result);
}
// Linear Search in C++
#include <iostream>
using namespace std;
int search(int array[], int n, int x) {
// Going through array sequencially
for (int i = 0; i < n; i++)
if (array[i] == x)
return i;
return -1;
}
int main() {
int array[] = {2, 4, 0, 1, 9};
int x = 1;
int n = sizeof(array) / sizeof(array[0]);
int result = search(array, n, x);
(result == -1) ? cout << "Element not found" : cout << "Element found at index: " << result;
}
Linear Search Complexities
Time Complexity: O(n)
Space Complexity: O(1)
Linear Search Applications
- For searching operations in smaller arrays (<100 items).