Learn Linear Search — Free DSA Tutorial

What is Linear Search

Linear search checks each element of a collection one at a time, from the first to the last, until it either finds the target value or reaches the end without finding it. It's the most straightforward search strategy and works regardless of whether the data is sorted.

Example: What is Linear Search

#include <iostream>
using namespace std;
int main() {
	int arr[] = {8, 3, 5, 1, 9};
	int target = 5;
	for (int i = 0; i < 5; i++) {
		if (arr[i] == target) { cout << "Found at index " << i; break; }
	}
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[] arr = {8, 3, 5, 1, 9};
		int target = 5;
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] == target) { System.out.println("Found at index " + i); break; }
		}
	}
}

arr = [8, 3, 5, 1, 9]
target = 5
for i, x in enumerate(arr):
    if x == target:
        print("Found at index", i)
        break

#include <stdio.h>
int main() {
	int arr[] = {8, 3, 5, 1, 9};
	int target = 5;
	for (int i = 0; i < 5; i++) {
		if (arr[i] == target) { printf("Found at index %d", i); break; }
	}
	return 0;
}

How It Works

The algorithm compares the target against the current element; if they match, the search stops and returns that position, and if not, it moves to the next element and repeats the comparison until either a match is found or the collection is exhausted.

Example: How It Works

#include <iostream>
using namespace std;
int main() {
	int arr[] = {8, 3, 5, 1, 9};
	int target = 1;
	for (int i = 0; i < 5; i++) {
		cout << "Checking index " << i << ": " << arr[i] << endl;
		if (arr[i] == target) { cout << "Match found"; break; }
	}
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[] arr = {8, 3, 5, 1, 9};
		int target = 1;
		for (int i = 0; i < arr.length; i++) {
			System.out.println("Checking index " + i + ": " + arr[i]);
			if (arr[i] == target) { System.out.println("Match found"); break; }
		}
	}
}

arr = [8, 3, 5, 1, 9]
target = 1
for i, x in enumerate(arr):
    print("Checking index", i, ":", x)
    if x == target:
        print("Match found")
        break

#include <stdio.h>
int main() {
	int arr[] = {8, 3, 5, 1, 9};
	int target = 1;
	for (int i = 0; i < 5; i++) {
		printf("Checking index %d: %d\n", i, arr[i]);
		if (arr[i] == target) { printf("Match found"); break; }
	}
	return 0;
}

Best and Worst Case

In the best case the target is the very first element checked, requiring just one comparison. In the worst case the target is the last element (or isn't present at all), requiring every single element to be checked before finishing.

Example: Best and Worst Case

#include <iostream>
using namespace std;
int main() {
	int arr[] = {8, 3, 5, 1, 9};
	cout << "Best case: target=8 found in 1 comparison. Worst case: target=9 found in 5 comparisons";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Best case: target=8 found in 1 comparison. Worst case: target=9 found in 5 comparisons");
	}
}

print("Best case: target=8 found in 1 comparison. Worst case: target=9 found in 5 comparisons")

#include <stdio.h>
int main() {
	printf("Best case: target=8 found in 1 comparison. Worst case: target=9 found in 5 comparisons");
	return 0;
}

Complexity

Linear search takes O(n) time in the worst case since it may need to examine every element, and O(1) extra space since it only needs to track the current position — no additional data structures are required.

Example: Complexity

#include <iostream>
using namespace std;
int main() {
	cout << "Linear search: O(n) worst-case time, O(1) extra space";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Linear search: O(n) worst-case time, O(1) extra space");
	}
}

print("Linear search: O(n) worst-case time, O(1) extra space")

#include <stdio.h>
int main() {
	printf("Linear search: O(n) worst-case time, O(1) extra space");
	return 0;
}

When to Use

Because it makes no assumptions about ordering, linear search is the right choice for unsorted data or data too small to bother sorting first; once data is sorted, faster options like binary search become worth the setup cost.

Example: When to Use

#include <iostream>
using namespace std;
int main() {
	cout << "Best for unsorted data or collections too small to justify sorting first";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Best for unsorted data or collections too small to justify sorting first");
	}
}

print("Best for unsorted data or collections too small to justify sorting first")

#include <stdio.h>
int main() {
	printf("Best for unsorted data or collections too small to justify sorting first");
	return 0;
}

Linear Search

What is Linear Search

How It Works

Best and Worst Case

Complexity

When to Use

Chapter Quiz — Complete all 5 topics to unlock

Login to run this code