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
linear_searchwalks from index 0 to n − 1 and compares each element withkey.- As soon as
a[i] == key, it returns i at once. No need to check the rest. - If the loop finishes, the key is not there, so it returns −1.
main()checks the result:-1means not found; anything else is the index. Position = index + 1 for humans.- 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:
| Step | low | high | mid | a[mid] | Decision |
|---|---|---|---|---|---|
| 1 | 0 | 8 | 4 | 23 | 23 < 72, go right: low = 5 |
| 2 | 5 | 8 | 6 | 56 | 56 < 72, go right: low = 7 |
| 3 | 7 | 8 | 7 | 72 | Found 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) / 2gives the same value as(low + high) / 2, but it cannot overflow when low and high are very large. Interviewers love this point.low = mid + 1andhigh = mid - 1: we skipmidbecause it is already checked. Writinglow = midcan cause an infinite loop.- The loop stops when
low > high: the search space is empty, so the key is not present.
Time Complexity of Linear and Binary Search
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.
| Case | Linear search | Binary search |
|---|---|---|
| Best case | O(1): key is first | O(1): key is in the middle |
| Average case | O(n) | O(log n) |
| Worst case | O(n) | O(log n) |
Difference Between Linear Search and Binary Search
| Point | Linear search | Binary search |
|---|---|---|
| Array must be sorted? | No | Yes |
| Method | Check one by one | Divide in half each time |
| Worst-case time | O(n) | O(log n) |
| Best for | Small or unsorted lists | Large sorted lists |
| Works on linked list? | Yes, easily | Not efficiently (no direct middle access) |
| Code | Very simple | A 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
| Mistake | What happens | Fix |
|---|---|---|
| Binary search on an unsorted array | Wrong "not found" results | Sort first, or use linear search |
while (low < high) | Misses the key when one element is left | while (low <= high) |
low = mid instead of mid + 1 | Infinite loop | low = mid + 1, high = mid - 1 |
| Printing "not found" inside the linear loop | Prints it many times | Decide only after the loop ends |
| Returning 0 for "not found" | Confused with index 0 | Return -1 |
Searching in Array Practice Questions
- What is the main condition for binary search?
- What is the worst-case time complexity of linear search and binary search?
- About how many comparisons does binary search need for 1024 elements in the worst case?
- Why is
mid = low + (high - low) / 2better than(low + high) / 2? - When is linear search a better choice than binary search?
Show answers
- The array must be sorted.
- Linear: O(n). Binary: O(log n).
- About 10 or 11 (log₂ 1024 = 10).
low + highcan overflow the int range for very large arrays; the other form cannot.- 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)
-
Binary search requires the array to be:
A) Large B) Sorted C) Of strings D) 2D
-
Worst-case time complexity of binary search:
A) O(n) B) O(1) C) O(log n) D) O(n²)
-
In a binary search, if
a[mid] < key, the next step is:A)
high = mid - 1B)low = mid + 1C)low = midD) Stop -
Linear search on 100 elements, worst-case comparisons:
A) 1 B) 7 C) 50 D) 100
-
Which search works on an unsorted array?
A) Binary B) Linear C) Both D) Neither
Show answers
- B: sorted.
- C: O(log n).
- B:
low = mid + 1. - D: 100.
- B: linear.
Quick Revision for Exams and Interviews
Read this before your exam. The highlighted words are the answer.
Must-remember facts
| Linear search | One by one, any array, O(n) |
|---|---|
| Binary search | Halve each time, sorted only, O(log n) |
| Not found | Return −1 |
| Safe mid | low + (high − low) / 2 |
| Loop condition | low <= 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.