What is Linear Search in C – C Programming Course With Examples

🚀 Learn BLE on Linux (BlueZ) – Programming Part 1

Hands-on Bluetooth Low Energy course. Special price: ₹399

Enroll Now on Udemy →
💬 Need help or career guidance? Ask us!Contact Us →

Free C Programming Course · Arrays · Lecture 10

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.

10
Arrays chapter
12 min
Read and practise
100%
Free forever

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 for loops, if and break
  • Basic knowledge of #define constants

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

ids10421756330217894127
checkednononoMATCH at index 3
resultstop here with break, 4 compares

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

foundelement equals targetset found_at = ibreak
not foundi reaches Nfound_at is still -1report not found

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 compares

Reading the output

QueryResultComparesWhy
330index 3, position 44Found after checking 104, 217, 56, 330
217index 1, position 22First of the two 217 entries wins, because break stops the loop
999not found8Every element had to be checked
104index 0, position 11Best 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.

CaseComparisonsExample with N = 8
Best case, first element1query 104
Worst case, last element or missingNquery 999 took 8
Average, value presentabout N / 2about 4

Linear search versus binary search

Elements NLinear search worst caseBinary search worst caseData must be sorted?
883Only for binary
1,0001,00010Only for binary
1,000,0001,000,00020Only 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

usesmall or unsorted table
answerlinear search
uselarge sorted table, many lookups
answerbinary search or a hash table

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

MistakeSymptomFix
Writing = instead of ==The array gets overwritten, always reports foundCompile with -Wall, it warns about assignment in a condition
Forgetting breakLoop reports the last match, wastes timeBreak at the first match when only one is needed
Confusing index and positionOff-by-one answers shown to the userAdd 1 only when printing for humans
Not handling not-foundUsing index -1 as an array subscriptAlways test the result before using it
Comparing floating-point values with ==Valid values are missed because of roundingCompare the absolute difference against a tolerance
Loop bound i <= NReads one element past the endUse 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

free c programming coursefree c tutorialc programming for embedded systemsembedded c programmingfree embedded c coursec arrays for beginnerslinear search in Csequential search arraysearch an array in embedded C

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 career guidance? Ask us!Contact Us →

1 Comment

Leave a Reply

Your email address will not be published. Required fields are marked *

×

🚀 BLE on Linux (BlueZ)

Hands-on course. Only ₹399

Enroll Now →