Need Help or More Information?
Questions about this free C programming course, embedded C training or career guidance? Get in touch.
Linear Search in C
Write linear search in C step by step: found and not-found cases, duplicates, comparison counts and when to prefer binary search in firmware.
Searching is one of the first algorithms every programmer learns, so this lecture of our free C programming course teaches linear search in C with real, tested programs.
You will see exactly how many comparisons each query needs, how to handle duplicates, and why this simple loop is still the right tool for the small tables found in microcontroller code.
What You Will Learn
- How linear search in C works and the two ways the loop can end
- Reporting index versus position correctly
- Finding the first match and finding every match
- Best, worst and average cost compared with binary search
- Real embedded uses such as command and ID tables
Prerequisites
- Earlier lectures of this arrays chapter
- Understanding of
forloops,ifandbreak - Basic knowledge of
#defineconstants
How Linear Search in C Works
Linear search is the most natural way to look for a value: start at the first element, compare it with what you want, and move to the next element until you either find a match or run out of elements. It is also called sequential search because it examines the elements in sequence. It does not need the data to be sorted, which is exactly why embedded programmers use it so often on small tables.
Searching for 330 in the ID table
The loop can end in exactly two ways. Either an element matched and we left early with break, or the loop counter ran off the end because nothing matched. Your code must tell these two cases apart. A classic way is to look at the loop counter after the loop, but a separate variable that holds the found index is clearer. We initialize it to -1, a value that can never be a valid index, and replace it when a match appears.
Two ways the loop ends
C Program for Linear Search
The program searches a table of eight device IDs for four different queries. Besides the result it counts the comparisons, so you can see the cost of the search with your own eyes. The table deliberately contains 217 twice.
#include <stdio.h>
#define N_IDS 8
#define N_QUERIES 4
int main(void)
{
int ids[N_IDS] = {104, 217, 56, 330, 217, 89, 412, 7};
int queries[N_QUERIES] = {330, 217, 999, 104};
int q, i;
for (q = 0; q < N_QUERIES; q++) {
int found_at = -1;
int compares = 0;
for (i = 0; i < N_IDS; i++) {
compares++;
if (ids[i] == queries[q]) {
found_at = i;
break;
}
}
if (found_at >= 0)
printf("id %3d -> index %d (position %d), %d compares\n",
queries[q], found_at, found_at + 1, compares);
else
printf("id %3d -> not found, %d compares\n", queries[q], compares);
}
return 0;
}$ gcc -std=c17 -Wall -Wextra -o ep_linear_search ep_linear_search.c
$ ./ep_linear_search
id 330 -> index 3 (position 4), 4 compares
id 217 -> index 1 (position 2), 2 compares
id 999 -> not found, 8 compares
id 104 -> index 0 (position 1), 1 comparesReading the output
| Query | Result | Compares | Why |
|---|---|---|---|
| 330 | index 3, position 4 | 4 | Found after checking 104, 217, 56, 330 |
| 217 | index 1, position 2 | 2 | First of the two 217 entries wins, because break stops the loop |
| 999 | not found | 8 | Every element had to be checked |
| 104 | index 0, position 1 | 1 | Best case, first element matches |
Pay attention to the difference between index and position. C counts from 0, so index 3 is the fourth element. Humans say position 4. Print the one your user expects, and never mix them silently.
Before you run the program, predict the output for query 217 on paper. You should say index 1 and two compares, because the first 217 sits second in the table and break ends the loop at once. Making a prediction first and checking it afterwards is the fastest way to build real understanding of loops, and it is exactly the skill that written tests and interviews measure.
Finding Every Match, Not Only the First
If duplicates matter, remove the break and handle each hit. The next program reports every index where 217 appears and counts the hits. Notice that the loop now always visits all N elements.
#include <stdio.h>
#define N_IDS 8
int main(void)
{
int ids[N_IDS] = {104, 217, 56, 330, 217, 89, 412, 217};
int target = 217;
int hits = 0;
int i;
printf("looking for %d:", target);
for (i = 0; i < N_IDS; i++) {
if (ids[i] == target) {
printf(" [%d]", i);
hits++;
}
}
printf("\nfound %d time(s)\n", hits);
return 0;
}$ gcc -std=c17 -Wall -Wextra -o ep_find_all ep_find_all.c
$ ./ep_find_all
looking for 217: [1] [4] [7]
found 3 time(s)How Fast Is Linear Search?
The work grows in a straight line with the size of the array, which is why it is called linear. The table shows how many comparisons you can expect for N elements.
| Case | Comparisons | Example with N = 8 |
|---|---|---|
| Best case, first element | 1 | query 104 |
| Worst case, last element or missing | N | query 999 took 8 |
| Average, value present | about N / 2 | about 4 |
Linear search versus binary search
| Elements N | Linear search worst case | Binary search worst case | Data must be sorted? |
|---|---|---|---|
| 8 | 8 | 3 | Only for binary |
| 1,000 | 1,000 | 10 | Only for binary |
| 1,000,000 | 1,000,000 | 20 | Only for binary |
Binary search is dramatically faster on big sorted data, but linear search wins when the table is small, unsorted or searched rarely. Sorting costs time and code space too, and on a table of ten command names a plain loop is the better engineering decision. We study binary search later in this course.
Choosing a search method
Real-World Uses in Embedded C Programming
- Command tables: match a received command code against a list of supported codes.
- Device or sensor IDs: check whether an address on an I2C bus is on your allowed list.
- CAN or protocol filters: test a message ID against a short list of accepted IDs.
- Error text lookup: turn a numeric error code into a message from a table.
- Pin permission checks: verify a GPIO number is in the list of pins your application may toggle.
Common Mistakes in Linear Search in C
| Mistake | Symptom | Fix |
|---|---|---|
Writing = instead of == | The array gets overwritten, always reports found | Compile with -Wall, it warns about assignment in a condition |
Forgetting break | Loop reports the last match, wastes time | Break at the first match when only one is needed |
| Confusing index and position | Off-by-one answers shown to the user | Add 1 only when printing for humans |
| Not handling not-found | Using index -1 as an array subscript | Always test the result before using it |
Comparing floating-point values with == | Valid values are missed because of rounding | Compare the absolute difference against a tolerance |
Loop bound i <= N | Reads one element past the end | Use i < N |
Best Practices for Linear Search in C
- Use a named constant for the table size, and let the loop and declaration share it.
- Return a clear sentinel such as -1 for not found, and document it.
- Performance: put the most frequently searched values near the front of the table, because the average cost then drops. For a hot path with hundreds of entries, consider a sorted table with binary search or a direct-indexed lookup table.
- Sentinel trick: if you own one spare slot at the end, store the target there first. The loop then needs no bound check, because a match is guaranteed. It is a classic micro-optimisation for tiny CPUs.
- Security: when you compare secrets such as a PIN or key, do not leave early on the first mismatch. An early exit makes the response time reveal how many characters were right. Use a constant-time comparison for secrets.
Summary and Key Takeaways
- Linear search checks elements one by one, so it works on unsorted data.
- Use a variable initialized to -1 to remember where the match was.
- Index starts at 0, position starts at 1, do not mix them.
- Cost is N compares in the worst case and about N / 2 on average.
- Perfect for small tables, replace it with binary search when data is large and sorted.
Conclusion
You can now write linear search in C, count its comparisons, report single or multiple matches and choose between linear and binary search with confidence. Searching a small table is a task you will repeat in almost every embedded C programming project. In the next lecture of our free C tutorial we start passing array elements into functions.
Topics Covered in This Free Embedded C Lecture
Frequently Asked Questions
What is linear search in C?
It is a search that compares the target with each array element in order until it finds a match or reaches the end. It works on unsorted data.
Why do you initialize the found index to -1?
Valid array indices are 0 or greater, so -1 can never be a real result. It safely means not found.
What is the time complexity of linear search?
It is O(N). The worst case examines all N elements, and on average about half of them when the value is present.
What is the difference between index and position?
Index counts from 0 as C does, position counts from 1 as people do. Position equals index plus 1.
When should I use binary search instead?
Use binary search when the array is sorted and large or searched often. For small unsorted tables, linear search is simpler and often faster in practice.
How do I find all occurrences of a value?
Do not break at the first match. Loop through every element, print or store each matching index and count the hits.
Continue the Free Embedded C Course
Next up: passing individual array elements to functions. Try changing the ID table and predict the compare counts before you run the program.
Need Help or More Information?
Questions about this free C programming course, embedded C training or career guidance? Get in touch.

1 Comment