Searching in C
Subject: Data Structures and Algorithms · Language: C · Level: intermediate · 6 min read
Learn linear search and binary search with sorted-array logic, index handling, and clean C code.
Searching means finding whether a value exists inside a collection. In C programming, searching is most commonly practiced with arrays.
If you want to find a roll number, a mark, a product id, or a target number inside a list, you need a searching technique.
Why Searching Is Important
Searching is one of the most basic operations in data structures. It is used in contact lists, databases, attendance records, product catalogs, dictionaries, and almost every application that stores data.
A good programmer should know which searching method is suitable for which situation.
Linear Search
Linear search checks elements one by one from the start. It works on both sorted and unsorted arrays.
If the target is found, the search returns the index. If the target is not found after checking all elements, it returns `-1`.
```c
for (int i = 0; i < n; i++) {
if (arr[i] == target) {
return i;
}
}
```
Linear search is easy to understand and works everywhere, but it can be slow for large arrays because it may need to check every element.
Binary Search
Binary search works only on sorted arrays. It repeatedly checks the middle element and removes half of the search space.
If the target is smaller than the middle element, search the left half. If it is greater, search the right half.
This makes binary search much faster than linear search for large sorted arrays.
Why Binary Search Needs Sorted Data
Binary search makes decisions based on order. If the middle element is greater than the target, it assumes the target can only be on the left side.
This assumption is true only when the array is sorted. If the array is unsorted, binary search can give a wrong result.
Search Result
Searching functions usually return the index if the element is found and `-1` if it is not found.
This makes it easy for the caller to check whether the search was successful.
Complete Searching Program
This program reads a sorted array and a target value, then searches using both linear search and binary search.
```c
#include <stdio.h>
int linearSearch(int arr[], int n, int target) {
for (int i = 0; i < n; i++) {
if (arr[i] == target) {
return i;
}
}
return -1;
}
int binarySearch(int arr[], int n, int target) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
return mid;
}
if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
int main(void) {
int n;
int arr[50];
int target;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter %d sorted elements: ", n);
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
printf("Enter target: ");
scanf("%d", &target);
printf("Linear search index = %d\n", linearSearch(arr, n, target));
printf("Binary search index = %d\n", binarySearch(arr, n, target));
return 0;
}
```
How Binary Search Moves
In binary search, `low` starts at the first index and `high` starts at the last index.
The middle index is calculated using `low + (high - low) / 2`. This is safer than `(low + high) / 2` for very large values.
If the target is greater than the middle element, `low` moves to `mid + 1`. If the target is smaller, `high` moves to `mid - 1`.
The loop stops when the target is found or when `low` becomes greater than `high`.
Linear Search vs Binary Search
- Linear search works on unsorted data
- Binary search needs sorted data
- Linear search checks one by one
- Binary search cuts the search area in half each time
Complexity
Linear search takes O(n) time. Binary search takes O(log n) time on sorted arrays.
For small arrays, linear search is often enough. For large sorted arrays, binary search is much better.
When to Use Which Search
Use linear search when data is small or unsorted. Use binary search when data is sorted and you need faster lookup.
If you must search many times, sorting the data first can be useful.
Index Note
C arrays use zero-based indexing. That means the first element is at index 0, the second element is at index 1, and so on.
So if the target 8 is the fourth element, the index printed is 3.
Practice Question
Write a C program that performs linear search on an unsorted array and prints `Found` or `Not found`.