Linear Search: flowchart, algorithm and program
This program reads n numbers into an array a, then reads a key and checks the elements one by one from the start. It prints the 1-based position of the first match, or "not found" if the key never appears.
▶ Watch the dry run step by step →
Algorithm
- Step 1: Start.
- Step 2: Set found = 0.
- Step 3: Read n.
- Step 4: Set i = 0.
- Step 5: If i < n, go to step 6; otherwise go to step 8.
- Step 6: Read a[i].
- Step 7: Set i = i + 1. Go to step 5.
- Step 8: Read key.
- Step 9: Set i = 0.
- Step 10: If i < n, go to step 11; otherwise go to step 15.
- Step 11: If a[i] == key, go to step 12; otherwise go to step 14.
- Step 12: Print "Found at position i+1".
- Step 13: Set found = 1. Go to step 15.
- Step 14: Set i = i + 1. Go to step 10.
- Step 15: If found == 0, go to step 16; otherwise go to step 17.
- Step 16: Print "not found".
- Step 17: Stop.
Program in C, Python and Java
Linear Search program in C
#include <stdio.h>
int main() {
int n, i, key, found = 0;
int a[100];
printf("Enter n: ");
scanf("%d", &n);
printf("Enter %d numbers: ", n);
for (i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
printf("Enter key: ");
scanf("%d", &key);
for (i = 0; i < n; i++) {
if (a[i] == key) {
printf("Found at position %d\n", i + 1);
found = 1;
break;
}
}
if (found == 0) {
printf("not found\n");
}
return 0;
}Linear Search program in Python
n = int(input("Enter n: "))
a = list(map(int, input("Enter " + str(n) + " numbers: ").split()))
key = int(input("Enter key: "))
found = 0
for i in range(n):
if a[i] == key:
print("Found at position", i + 1)
found = 1
break
if found == 0:
print("not found")Linear Search program in Java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n, i, key, found = 0;
System.out.print("Enter n: ");
n = sc.nextInt();
int[] a = new int[n];
System.out.print("Enter " + n + " numbers: ");
for (i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
System.out.print("Enter key: ");
key = sc.nextInt();
for (i = 0; i < n; i++) {
if (a[i] == key) {
System.out.println("Found at position " + (i + 1));
found = 1;
break;
}
}
if (found == 0) {
System.out.println("not found");
}
}
}
Sample input: n = 5, numbers = 10 25 30 45 50, key = 30
Output: Found at position 3
How it works
- The first loop reads n numbers into a[0] to a[n-1].
- The variable found starts at 0. It is a flag that remembers whether the key has been seen.
- The second loop goes through i = 0, 1, 2, ... and compares a[i] with key.
- When a[i] == key, the program prints i + 1 (arrays start at index 0, but people count from 1), sets found = 1 and uses break to stop.
- After the loop, if found is still 0, no element matched, so it prints "not found".
- In the sample, a[0] = 10 and a[1] = 25 do not match, a[2] = 30 matches, so it prints position 3.
Dry run (trace table)
| Step | Line | Box | found | n | i | a[0] | a[1] | a[2] | a[3] | a[4] | key | Output |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 3 | Start | ||||||||||
| 2 | 4 | found = 0 | 0 | |||||||||
| 3 | 7 | Read n | 0 | 5 | Enter n: | |||||||
| 4 | 9 | i = 0 | 0 | 5 | 0 | Enter 5 numbers: | ||||||
| 5 | 9 | i < n? | 0 | 5 | 0 | |||||||
| 6 | 10 | Read a[i] | 0 | 5 | 0 | 10 | ||||||
| 7 | 9 | i = i + 1 | 0 | 5 | 1 | 10 | ||||||
| 8 | 9 | i < n? | 0 | 5 | 1 | |||||||
| 9 | 10 | Read a[i] | 0 | 5 | 1 | 25 | ||||||
| 10 | 9 | i = i + 1 | 0 | 5 | 2 | |||||||
| 11 | 9 | i < n? | 0 | 5 | 2 | |||||||
| 12 | 10 | Read a[i] | 0 | 5 | 2 | 30 | ||||||
| 13 | 9 | i = i + 1 | 0 | 5 | 3 | |||||||
| 14 | 9 | i < n? | 0 | 5 | 3 | |||||||
| 15 | 10 | Read a[i] | 0 | 5 | 3 | 45 | ||||||
| 16 | 9 | i = i + 1 | 0 | 5 | 4 | |||||||
| 17 | 9 | i < n? | 0 | 5 | 4 | |||||||
| 18 | 10 | Read a[i] | 0 | 5 | 4 | 50 | ||||||
| 19 | 9 | i = i + 1 | 0 | 5 | 5 | |||||||
| 20 | 9 | i < n? | 0 | 5 | 5 |
Time and space complexity
Time: O(n) · Space: O(n). Each loop visits at most n elements doing constant work, and the array stores n numbers.
Common mistakes
- Printing i instead of i + 1, which gives the index (2) and not the position (3).
- Forgetting break, so the loop keeps going and prints every match when the key appears more than once.
- Printing "not found" inside the loop's else branch, which prints it for every non-matching element instead of once after the loop.
Viva questions
Q1. Why is the variable `found` initialised to 0, and what does it do?
It is a flag meaning 'key not found yet'. It stays 0 unless a match is seen, and the loop sets it to 1 on a match. After the loop, `found == 0` tells us to print 'not found'.
Q2. Why does the program print `i + 1` and not `i`?
Array indices start at 0, but people count positions from 1. So the element at index 0 is reported as position 1.
Q3. What is the use of `break` on line 18?
It stops the search as soon as the first match is found, so the rest of the array is not scanned. It also means only the first occurrence of a repeated key is reported.
Q4. What happens if the key appears more than once in the array?
Only the first position is printed, because `break` exits the loop after the first match. To report all positions, remove `break` and keep the `found` flag.
Q5. What happens if n is 0, or if the user enters a negative n?
For n = 0 or negative, the loop condition `i < n` is false straight away, so nothing is read or searched and 'not found' is printed. A bigger problem is n greater than 100, which overflows the array `a[100]`, and the program does not check for this.
Q6. What is the time complexity of linear search, and what are the best and worst cases?
It is O(n). The best case is O(1) when the key is the first element. The worst case is n comparisons, when the key is last or absent.
Q7. Does linear search need the array to be sorted? How does it differ from binary search?
No, linear search works on unsorted data because it checks every element in turn. Binary search needs a sorted array and halves the range each step, giving O(log n).
Q8. What would you change to make the program return the count of how many times the key occurs?
Replace the `found` flag with a counter, increment it on each match, and remove the `break` so the whole array is scanned. Then print the count, and print 'not found' if it is 0.
Frequently asked questions
What is the time complexity of linear search?
The worst case is O(n), when the key is last or missing, because every element is checked. The best case is O(1), when the key is the first element.
Does linear search need a sorted array?
No. It checks elements one by one, so the order of the numbers does not matter. Binary search is the one that needs sorted data.
What if the key appears more than once?
This program reports only the first match, because break stops the loop right after it. Remove the break to print every position.