Linear Search Algorithm Sequential Search is an important DAA topic because it appears in real projects, debugging sessions, and interviews. Learn the meaning first, then connect it to a small working example so the rule does not stay abstract.
For this page, focus on what problem Linear Search Algorithm Sequential Search solves, where developers usually make mistakes, and how to verify the result. The audit note for this lesson was: limited checklist/practice/mistake/FAQ notes .
A strong understanding of Linear Search Algorithm Sequential Search should include syntax, behavior, one realistic use case, one failure case, and one quick way to check your work with tools or output.
Linear Search Algorithm Sequential Search should be studied as a practical algorithm analysis lesson, not as a label. Start by naming the input, the rule that changes the input, and the result a learner should be able to predict after reading the page.
In the daa > linear-search page, the notes should connect the definition with a working scenario, a mistake that beginners actually make, and the exact check that proves the fix. That makes the topic useful for coding, debugging, and interview revision.
Linear search (also called sequential search) is the simplest and most straightforward searching algorithm. It works by checking each element of the array sequentially from the beginning to the end until the target element is found or the entire array has been traversed. Unlike binary search, linear search doesn't require the array to be sorted, making it versatile for any type of data structure.
The algorithm starts at the first element (index 0) and compares it with the target value. If they match, the search is successful and the index is returned. If not, it moves to the next element and repeats the process. This continues until either the target is found or all elements have been checked.
Consider searching for the number 7 in the array: [5, 3, 8, 1, 9, 2, 7, 4, 6]
Where n is the number of elements in the array. In the worst case, we need to check all n elements, making it a linear time algorithm.
| Case | Time Complexity | When It Occurs | Example |
|---|---|---|---|
| Best Case | O(1) | Target is the first element | Search 5 in [5, 3, 8, 1] |
| Average Case | O(n/2) ~= O(n) | Target is in the middle | Search 8 in [5, 3, 8, 1, 9] |
| Worst Case | O(n) | Target is last or not present | Search 9 in [5, 3, 8, 1, 9] |
| Space Complexity | O(1) | No extra memory needed | Only uses a few variables |
public class LinearSearch {
// Iterative linear search - O(n) time, O(1) space
static int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return i; // Found at index i
}
}
return -1; // Not found
}
// Recursive linear search - O(n) time, O(n) space (call stack)
static int linearSearchRec(int[] arr, int index, int target) {
// Base case 1: Reached end of array
if (index == arr.length) {
return -1; // Not found
}
// Base case 2: Found the target
if (arr[index] == target) {
return index;
}
// Recursive case: Search in remaining array
return linearSearchRec(arr, index + 1, target);
}
// Find ALL occurrences of target
static void findAllOccurrences(int[] arr, int target) {
boolean found = false;
System.out.print("Indices where " + target + " is found: ");
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
System.out.print(i + " ");
found = true;
}
}
if (!found) {
System.out.print("Not found");
}
System.out.println();
}
// Linear search with custom comparator (for objects)
static <T> int linearSearchGeneric(T[] arr, T target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i].equals(target)) {
return i;
}
}
return -1;
}
public static void main(String[] args) {
int[] arr = {5, 3, 8, 1, 9, 2, 7, 4, 6};
// Test iterative search
System.out.println("Array: [5, 3, 8, 1, 9, 2, 7, 4, 6]");
System.out.println("Search 7: index " + linearSearch(arr, 7)); // 6
System.out.println("Search 10: index " + linearSearch(arr, 10)); // -1
// Test recursive search
System.out.println("Recursive search 9: index " +
linearSearchRec(arr, 0, 9)); // 4
// Test find all occurrences
int[] arr2 = {3, 1, 4, 1, 5, 9, 2, 6, 1};
System.out.println("\nArray: [3, 1, 4, 1, 5, 9, 2, 6, 1]");
findAllOccurrences(arr2, 1); // Indices: 1 3 8
// Test with strings
String[] names = {"Alice", "Bob", "Charlie", "David"};
System.out.println("\nSearch 'Charlie': index " +
linearSearchGeneric(names, "Charlie")); // 2
}
}
/*
* Trace for arr = {5, 3, 8, 1, 9}, target = 9:
*
* i=0: arr[0]=5 != 9 -> continue
* i=1: arr[1]=3 != 9 -> continue
* i=2: arr[2]=8 != 9 -> continue
* i=3: arr[3]=1 != 9 -> continue
* i=4: arr[4]=9 = 9 -> return 4 [ok]
*/# Linear Search in Python
def linear_search(arr, target):
"""Iterative linear search - O(n) time, O(1) space"""
for i in range(len(arr)):
if arr[i] == target:
return i # Found at index i
return -1 # Not found
def linear_search_recursive(arr, index, target):
"""Recursive linear search - O(n) time, O(n) space"""
# Base case 1: Reached end of array
if index == len(arr):
return -1
# Base case 2: Found the target
if arr[index] == target:
return index
# Recursive case
return linear_search_recursive(arr, index + 1, target)
def find_all_occurrences(arr, target):
"""Find all indices where target appears"""
indices = [i for i, val in enumerate(arr) if val == target]
return indices if indices else [-1]
# Test the functions
if __name__ == "__main__":
arr = [5, 3, 8, 1, 9, 2, 7, 4, 6]
print("Array:", arr)
print("Search 7:", linear_search(arr, 7)) # 6
print("Search 10:", linear_search(arr, 10)) # -1
print("Recursive search 9:", linear_search_recursive(arr, 0, 9)) # 4
arr2 = [3, 1, 4, 1, 5, 9, 2, 6, 1]
print("\nArray:", arr2)
print("All occurrences of 1:", find_all_occurrences(arr2, 1)) # [1, 3, 8]#include <stdio.h>
// Iterative linear search - O(n) time, O(1) space
int linearSearch(int arr[], int n, int target) {
for (int i = 0; i < n; i++) {
if (arr[i] == target) {
return i; // Found at index i
}
}
return -1; // Not found
}
// Recursive linear search - O(n) time, O(n) space
int linearSearchRec(int arr[], int index, int n, int target) {
// Base case 1: Reached end of array
if (index == n) {
return -1;
}
// Base case 2: Found the target
if (arr[index] == target) {
return index;
}
// Recursive case
return linearSearchRec(arr, index + 1, n, target);
}
int main() {
int arr[] = {5, 3, 8, 1, 9, 2, 7, 4, 6};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Array: [5, 3, 8, 1, 9, 2, 7, 4, 6]\n");
printf("Search 7: index %d\n", linearSearch(arr, n, 7)); // 6
printf("Search 10: index %d\n", linearSearch(arr, n, 10)); // -1
printf("Recursive search 9: index %d\n",
linearSearchRec(arr, 0, n, 9)); // 4
return 0;
}| Step | Action | Description |
|---|---|---|
| 1 | Start from index 0 | Begin at the first element of the array |
| 2 | Compare current element with target | Check if arr[i] == target |
| 3 | If match found | Return the current index i |
| 4 | If no match | Move to next element (i++) |
| 5 | Repeat steps 2-4 | Continue until target found or array ends |
| 6 | If array exhausted | Return -1 (not found) |
| Use Linear Search When | Use Binary Search When |
|---|---|
| Array is unsorted | Array is sorted |
| Array size is small (< 100 elements) | Array size is large (> 1000 elements) |
| Data structure is a linked list | Data structure is an array |
| Searching is infrequent | Searching is frequent |
| Simplicity is more important than speed | Performance is critical |
| Data changes frequently (no time to sort) | Data is static or rarely changes |
| Feature | Linear Search | Binary Search |
|---|---|---|
| Array requirement | Unsorted or sorted | Must be sorted |
| Time complexity (Best) | O(1) | O(1) |
| Time complexity (Average) | O(n) | O(log n) |
| Time complexity (Worst) | O(n) | O(log n) |
| Space complexity | O(1) | O(1) iterative, O(log n) recursive |
| Implementation | Very simple | More complex |
| Best for | Small or unsorted data | Large sorted data |
| Data structure | Arrays, linked lists | Arrays only |
| Example (n=1000) | ~500 comparisons (average) | ~10 comparisons (average) |
For an array of size n = 1,000,000:
This shows why binary search is dramatically faster for large sorted datasets. However, if the array is unsorted, sorting it first takes O(n log n) time, which might make linear search more efficient for a single search operation.
1. Define the input for Linear Search Algorithm Sequential Search.
2. Apply the rule from the lesson.
3. Compare the actual result with the expected result.
4. Record the fix if the result differs.1. Try empty, missing, duplicate, or invalid data.
2. Identify where Linear Search Algorithm Sequential Search changes behavior.
3. Explain the safest correction.
4. Retest the normal path.Memorizing Linear Search Algorithm Sequential Search without the situation where it is useful.
Connect Linear Search Algorithm Sequential Search to a concrete algorithm analysis task.
Testing Linear Search Algorithm Sequential Search only with the perfect input.
Include empty, missing, duplicate, incompatible, or failed cases when relevant.
Changing code before reading the visible symptom or error message.
Inspect the output, state, configuration, or stack trace connected to Linear Search Algorithm Sequential Search.
Memorizing Linear Search Algorithm Sequential Search without the situation where it is useful.
Connect Linear Search Algorithm Sequential Search to a concrete algorithm analysis task.
The common mistake is memorizing syntax without understanding when the behavior changes or fails.
Remember the problem it solves in algorithm analysis, then attach the syntax or steps to that problem.
You can predict the result of a small example, explain a failure case, and choose it over a nearby alternative for a clear reason.
They often copy the syntax but skip the state, input, dependency, selector, route, type, or configuration that controls the behavior.
Explore 500+ free tutorials across 20+ languages and frameworks.