Skip to content
StudyFame

Linear and Binary Search in C

How do you find a word in a dictionary? You don't read every page from the start. You open the middle, see if the word comes before or after, and throw away half the book. That is binary search.

But if the pages were shuffled, you would have to check them one by one. That is linear search. In this lesson you will write both programs and learn when to use which, a favourite exam and interview question.

What You Will Learn

  • What searching means.
  • How linear search works, with a program.
  • How binary search works, with a dry run and a program.
  • Why binary search needs a sorted array.
  • Time complexity and the difference between the two.

Linear Search and Binary Search Explained

Exam definition: Linear search checks each element one by one from the start until the key is found or the array ends. Binary search works on a sorted array: it compares the key with the middle element and repeatedly searches only the half where the key can be.

Memory trick: Linear = line by line, like checking every house on a street for your friend. Binary = bi means two: every step cuts the list into two halves, like the dictionary.

  • Key: the value you are looking for.
  • Both searches return the index where the key is found, or −1 if it isn't there (−1 is never a valid index).

Binary search algorithm

low = 0, high = n-1
while low <= high:
    mid = low + (high - low) / 2
    if a[mid] == key   -> found at mid, stop
    if a[mid] <  key   -> key is on the right: low  = mid + 1
    else               -> key is on the left : high = mid - 1
not found -> return -1

Example 1: Linear Search Program in C

#include <stdio.h>

int linear_search(const int a[], int n, int key)
{
    int i;
    for (i = 0; i < n; i++)
    {
        if (a[i] == key)
            return i;           /* found: return its index */
    }
    return -1;                  /* checked everything: not found */
}

int main(void)
{
    int a[] = {42, 17, 8, 93, 25, 61};
    int n = sizeof(a) / sizeof(a[0]);
    int pos;

    pos = linear_search(a, n, 93);
    if (pos != -1)
        printf("93 found at index %d (position %d)\n", pos, pos + 1);

    pos = linear_search(a, n, 50);
    if (pos == -1)
        printf("50 not found\n");

    return 0;
}

Output

93 found at index 3 (position 4)
50 not found

Code Explanation

  1. linear_search walks from index 0 to n − 1 and compares each element with key.
  2. As soon as a[i] == key, it returns i at once. No need to check the rest.
  3. If the loop finishes, the key is not there, so it returns −1.
  4. main() checks the result: -1 means not found; anything else is the index. Position = index + 1 for humans.
  5. Linear search works on any array, sorted or not.

How Binary Search Works (Dry Run)

Search for key = 23 in the sorted array:

index :  0   1   2   3   4   5   6   7   8
value :  3   8  12  16  23  38  56  72  91

Step 1: low=0 high=8 mid=4  a[4]=23 == 23  -> FOUND in 1 step

Now search for key = 72:

Steplowhighmida[mid]Decision
10842323 < 72, go right: low = 5
25865656 < 72, go right: low = 7
378772Found at index 7

Linear search would need 8 comparisons for 72. Binary search needed only 3.

Example 2: Binary Search Program in C

#include <stdio.h>

int binary_search(const int a[], int n, int key)
{
    int low = 0, high = n - 1, mid, steps = 0;

    while (low <= high)
    {
        mid = low + (high - low) / 2;
        steps++;
        if (a[mid] == key)
        {
            printf("(%d steps) ", steps);
            return mid;
        }
        else if (a[mid] < key)
            low = mid + 1;        /* search the right half */
        else
            high = mid - 1;       /* search the left half */
    }
    printf("(%d steps) ", steps);
    return -1;
}

int main(void)
{
    int a[] = {3, 8, 12, 16, 23, 38, 56, 72, 91};
    int n = sizeof(a) / sizeof(a[0]);
    int keys[] = {72, 3, 40};
    int i, pos;

    for (i = 0; i < 3; i++)
    {
        printf("Search %d: ", keys[i]);
        pos = binary_search(a, n, keys[i]);
        if (pos != -1)
            printf("found at index %d\n", pos);
        else
            printf("not found\n");
    }

    return 0;
}

Output

Search 72: (3 steps) found at index 7
Search 3: (3 steps) found at index 0
Search 40: (3 steps) not found
  • mid = low + (high - low) / 2 gives the same value as (low + high) / 2, but it cannot overflow when low and high are very large. Interviewers love this point.
  • low = mid + 1 and high = mid - 1: we skip mid because it is already checked. Writing low = mid can cause an infinite loop.
  • The loop stops when low > high: the search space is empty, so the key is not present.

Each binary search step halves the list. For 1,000 elements: 1000 → 500 → 250 → 125 → 63 → 32 → 16 → 8 → 4 → 2 → 1, about 10 steps. For 10 lakh elements, only about 20 steps. That is log₂ n.

CaseLinear searchBinary search
Best caseO(1): key is firstO(1): key is in the middle
Average caseO(n)O(log n)
Worst caseO(n)O(log n)
PointLinear searchBinary search
Array must be sorted?NoYes
MethodCheck one by oneDivide in half each time
Worst-case timeO(n)O(log n)
Best forSmall or unsorted listsLarge sorted lists
Works on linked list?Yes, easilyNot efficiently (no direct middle access)
CodeVery simpleA little more careful

Important Points to Remember

  • Linear search works on any array; binary search needs a sorted array.
  • Return −1 for "not found".
  • Use mid = low + (high − low) / 2 to avoid overflow.
  • Loop condition is low <= high, not low < high.
  • Linear: O(n). Binary: O(log n).
  • If you search many times, sort once then use binary search.

Common Mistakes Beginners Make

MistakeWhat happensFix
Binary search on an unsorted arrayWrong "not found" resultsSort first, or use linear search
while (low < high)Misses the key when one element is leftwhile (low <= high)
low = mid instead of mid + 1Infinite looplow = mid + 1, high = mid - 1
Printing "not found" inside the linear loopPrints it many timesDecide only after the loop ends
Returning 0 for "not found"Confused with index 0Return -1

Searching in Array Practice Questions

  1. What is the main condition for binary search?
  2. What is the worst-case time complexity of linear search and binary search?
  3. About how many comparisons does binary search need for 1024 elements in the worst case?
  4. Why is mid = low + (high - low) / 2 better than (low + high) / 2?
  5. When is linear search a better choice than binary search?
Show answers
  1. The array must be sorted.
  2. Linear: O(n). Binary: O(log n).
  3. About 10 or 11 (log₂ 1024 = 10).
  4. low + high can overflow the int range for very large arrays; the other form cannot.
  5. When the array is small, unsorted and searched only once, or when the data is in a linked list.

Coding Exercise

Modify linear search to count how many times a key appears and print all its positions. Test with {5, 3, 5, 9, 5, 1} and key 5.

Show solution
#include <stdio.h>

int main(void)
{
    int a[] = {5, 3, 5, 9, 5, 1};
    int n = 6, key = 5, i, count = 0;

    printf("%d found at index:", key);
    for (i = 0; i < n; i++)
    {
        if (a[i] == key)
        {
            printf(" %d", i);
            count++;
        }
    }
    printf("\nTotal: %d times\n", count);
    return 0;
}
5 found at index: 0 2 4
Total: 3 times

Quick Quiz: Linear and Binary Search (MCQ)

  1. Binary search requires the array to be:

    A) Large   B) Sorted   C) Of strings   D) 2D

  2. Worst-case time complexity of binary search:

    A) O(n)   B) O(1)   C) O(log n)   D) O(n²)

  3. In a binary search, if a[mid] < key, the next step is:

    A) high = mid - 1   B) low = mid + 1   C) low = mid   D) Stop

  4. Linear search on 100 elements, worst-case comparisons:

    A) 1   B) 7   C) 50   D) 100

  5. Which search works on an unsorted array?

    A) Binary   B) Linear   C) Both   D) Neither

Show answers
  1. B: sorted.
  2. C: O(log n).
  3. B: low = mid + 1.
  4. D: 100.
  5. B: linear.

Quick Revision for Exams and Interviews

Read this before your exam. The highlighted words are the answer.

Must-remember facts

Linear searchOne by one, any array, O(n)
Binary searchHalve each time, sorted only, O(log n)
Not foundReturn −1
Safe midlow + (high − low) / 2
Loop conditionlow <= high
Best case (both)O(1)

Frequently asked questions

What is the difference between linear and binary search?
Linear checks each element (O(n), any order); binary halves a sorted array each step (O(log n)).
Why does binary search need a sorted array?
Only in sorted order can one comparison tell which half to throw away.
Why use low + (high − low) / 2?
It avoids integer overflow of low + high.

Remember

  • Linear = house to house; binary = dictionary.
  • Binary search? First ask: is it sorted?

Next Topic

Next lesson: Sorting an Array in C. You will sort an array with bubble sort and selection sort, so binary search can work on it.