Linear Search vs Binary Search in C: Key Differences and Code Examples

In C, linear search checks each element one by one and works on unsorted arrays, while binary search divides the array in half repeatedly but requires a sorted array. Binary search is faster with large sorted data, but linear search is simpler and works on any array.

Quick Comparison

Here is a quick side-by-side comparison of linear search and binary search in C.

Factor	Linear Search	Binary Search
Data Requirement	Works on unsorted arrays	Requires sorted arrays
Method	Checks elements one by one	Divides array repeatedly in half
Time Complexity	O(n) - linear time	O(log n) - logarithmic time
Implementation	Simple and straightforward	More complex with recursion or loops
Use Case	Small or unsorted data	Large sorted data for faster search
Performance	Slower on large data	Much faster on large data

Key Differences

Linear search scans each element from start to end until it finds the target or reaches the array's end. It does not require the array to be sorted, making it flexible but slower for large data because it may check every element.

Binary search works only on sorted arrays. It repeatedly splits the search range in half by comparing the middle element to the target. This reduces the search space quickly, making it much faster for large arrays but requiring the data to be sorted first.

In C, linear search is easier to implement with a simple loop, while binary search often uses recursion or a loop with careful index management. Choosing between them depends on whether the data is sorted and how large the array is.

Code Comparison

This C code shows how to perform a linear search to find a number in an array.

c

#include <stdio.h>

int linear_search(int arr[], int size, int target) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) {
            return i; // Return index if found
        }
    }
    return -1; // Not found
}

int main() {
    int data[] = {5, 3, 8, 4, 2};
    int target = 4;
    int size = sizeof(data) / sizeof(data[0]);

    int result = linear_search(data, size, target);
    if (result != -1) {
        printf("Element %d found at index %d\n", target, result);
    } else {
        printf("Element %d not found\n", target);
    }
    return 0;
}

Output

Element 4 found at index 3

Binary Search Equivalent

This C code shows how to perform a binary search on a sorted array to find a number.

c

#include <stdio.h>

int binary_search(int arr[], int size, int target) {
    int left = 0;
    int right = size - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid; // Found target
        } else if (arr[mid] < target) {
            left = mid + 1; // Search right half
        } else {
            right = mid - 1; // Search left half
        }
    }
    return -1; // Not found
}

int main() {
    int data[] = {2, 3, 4, 5, 8}; // Sorted array
    int target = 4;
    int size = sizeof(data) / sizeof(data[0]);

    int result = binary_search(data, size, target);
    if (result != -1) {
        printf("Element %d found at index %d\n", target, result);
    } else {
        printf("Element %d not found\n", target);
    }
    return 0;
}

Output

Element 4 found at index 2

When to Use Which

Choose linear search when your data is small or unsorted, and simplicity is important. It works without any preparation and is easy to implement.

Choose binary search when your data is large and sorted, and you need faster search times. Although it requires sorted data and a bit more complex code, it significantly reduces search time on big arrays.

In summary, use linear search for quick, simple checks and binary search for efficient searching in sorted data.

Key Takeaways

Linear search works on any array but is slower for large data with O(n) time.

Binary search requires sorted arrays but is much faster with O(log n) time.

Linear search is simpler to code and good for small or unsorted data.

Binary search is best for large, sorted data where performance matters.

Choose the search method based on data size and whether the array is sorted.