October 17, 2026

Introduction

Searching is one of the most fundamental operations in Data Structures and Algorithms (DSA). It is the process of finding a specific element in a collection of data and determining whether it exists and, if found, where it is located.

Searching algorithms are used in student management systems, banking applications, inventory software, databases, and many other computer applications.

For example, when a user searches for a student's roll number in a college management system, the software must locate the corresponding record. The efficiency of this operation depends on how the data is organized and which searching algorithm is used.

In this module, you will learn:

1. Linear Search

2. Binary Search

3. Iterative vs Recursive Binary Search

4. Time Complexity Comparison

All examples use the C programming language.

1. Linear Search in C

What Is Linear Search?

Linear Search is a searching algorithm that checks elements one by one, starting from the first element, until the target is found or all elements have been examined.

It is also called sequential search because elements are checked sequentially.

The main advantage of linear search is that it works with both sorted and unsorted arrays.

How Linear Search Works

Suppose we have the following array:

[10, 25, 30, 45, 50]

We want to search for the value 45.

The algorithm checks the elements in this order:

1. Compare 45 with 10. They are not equal.

2. Compare 45 with 25. They are not equal.

3. Compare 45 with 30. They are not equal.

4. Compare 45 with 45. The target is found at index 3.

Because C arrays use zero-based indexing, the fourth element has index 3.

Algorithm for Linear Search

1. Start from index zero.

2. Compare the current element with the target.

3. If they match, return the index.

4. Otherwise, move to the next element.

5. If the end of the array is reached without a match, report that the target was not found.

C Program: Linear Search

#include 

int linearSearch(const int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i;
        }
    }

    return -1;
}

int main(void) {
    int arr[] = {10, 25, 30, 45, 50};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 45;

    int result = linearSearch(arr, n, target);

    if (result != -1) {
        printf("Element found at index %d\n", result);
    } else {
        printf("Element not found\n");
    }

    return 0;
}

Output:

Element found at index 3

Explanation of the Program

• linearSearch() receives the array, its size, and the target value.

• The for loop visits each element from index 0 to n - 1.

• arr[i] == target checks whether the current element matches the target.

• If a match is found, the function returns the index immediately.

• If no match exists, the function returns -1.

• The main() function displays the search result.

Returning -1 is a common convention for indicating that a value was not found, because -1 is not a valid array index.

Time and Space Complexity of Linear Search

Best-case time complexity: (O(1))

The target is at the first position, so only one comparison is needed.

Average-case time complexity: (O(n))

Under the assumption that the target is equally likely to occur at any position, a successful search examines approximately half the elements on average. The growth rate is still linear.

Worst-case time complexity: (O(n))

The target is at the last position or is not present, requiring up to n comparisons.

Auxiliary space complexity: (O(1))

The iterative algorithm uses only a constant amount of additional memory.

Advantages of Linear Search

• Simple to understand and implement.

• Works with sorted and unsorted data.

• Does not require preprocessing or sorting.

• Suitable for small collections.

Disadvantages of Linear Search

• Can be slow for large collections.

• May need to inspect every element.

• Becomes less attractive when searches are frequent and faster lookup methods are available.

Real-World Applications

Linear search is useful when:

• The collection is small.

• Data is unsorted.

• Only a few searches are required.

• Sorting the data first would cost more than searching it directly.

2. Binary Search in C

What Is Binary Search?

Binary Search is an efficient searching algorithm that repeatedly divides a search interval into two halves to locate a target value.

Unlike linear search, binary search requires the array to be sorted in the order being searched.

For an ascending array, the elements must be arranged from smallest to largest.

Binary search is especially useful for large, sorted arrays because its search interval decreases rapidly after each comparison.

How Binary Search Works

Consider the sorted array:

[10, 20, 30, 40, 50, 60, 70]

Suppose we want to search for 60.

Initially:

• low = 0

• high = 6

Calculate the middle index:

[
mid = low + \frac{high-low}{2}
]

Therefore:

[
mid = 0 + \frac{6-0}{2} = 3
]

The middle element is 40.

Since 60 is greater than 40, the target can only be in the right half. Set low = mid + 1, giving low = 4.

The remaining search interval is:

[50, 60, 70]

The middle index of this interval is 5, and the element at index 5 is 60.

The target is found at index 5.

Algorithm for Binary Search

1. Initialize low to 0.

2. Initialize high to n - 1.

3. While low <= high, calculate the middle index.

4. If the middle element equals the target, return its index.

5. If the target is greater than the middle element, search the right half.

6. Otherwise, search the left half.

7. If the search interval becomes empty, return -1.

C Program: Iterative Binary Search

#include 

int binarySearch(const 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;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return -1;
}

int main(void) {
    int arr[] = {10, 20, 30, 40, 50, 60, 70};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 60;

    int result = binarySearch(arr, n, target);

    if (result != -1) {
        printf("Element found at index %d\n", result);
    } else {
        printf("Element not found\n");
    }

    return 0;
}

Output:

Element found at index 5

Explanation of the Program

• low identifies the first index of the current search interval.

• high identifies the last index of the current search interval.

• mid identifies the middle index.

• If arr[mid] matches the target, the function returns the index.

• If the target is larger than arr[mid], the left portion can be discarded.

• If the target is smaller than arr[mid], the right portion can be discarded.

• If low becomes greater than high, the target is not present.

The expression low + (high - low) / 2 is preferred over (low + high) / 2 because it reduces the risk of integer overflow when calculating the middle index.

Time Complexity of Binary Search

Best-case time complexity: (O(1))

The target matches the first middle element examined.

Average-case time complexity: (O(\log n))

The search interval is repeatedly reduced by approximately half.

Worst-case time complexity: (O(\log n))

The algorithm continues halving the interval until the target is found or the interval becomes empty.

Auxiliary space complexity: (O(1))

The iterative implementation uses a fixed number of variables.

Why Is Binary Search Faster?

Suppose an array contains 1,024 elements.

Linear search may require up to 1,024 comparisons in the worst case.

Binary search reduces the interval approximately as follows:

1024 → 512 → 256 → 128 → 64 → ... → 1

Only about 11 middle-element checks are needed to reduce an interval of 1,024 elements to one candidate, and a successful search can finish even earlier.

This logarithmic growth is why binary search is often much faster than linear search on large, sorted arrays.

Advantages of Binary Search

• Efficient for large, sorted arrays.

• Has logarithmic worst-case search time.

• Requires only a constant amount of auxiliary space when implemented iteratively.

Disadvantages of Binary Search

• The input must be sorted.

• Maintaining sorted data can add costs when frequent insertions and deletions are required.

• It is not directly suitable for linked lists when efficient middle-element access is unavailable.

3. Iterative vs Recursive Binary Search

Binary search can be implemented in two ways:

• Iterative binary search: Uses a loop to repeatedly reduce the search interval.

• Recursive binary search: Uses function calls to search smaller intervals.

Both implementations follow the same fundamental logic. The difference is how repeated steps are expressed in the program.

3.1 Iterative Binary Search

An iterative algorithm repeats operations using a loop, such as while or for.

In iterative binary search, the low and high variables are updated inside the loop until the target is found or the interval becomes empty.

Example:

int binarySearchIterative(const 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;
}

The function updates the search interval without making additional recursive calls.

3.2 Recursive Binary Search

Recursion occurs when a function calls itself to solve a smaller version of the same problem.

In recursive binary search, each function call searches either the left half or the right half of the current interval.

A recursive implementation must include a base case to stop the recursion.

The two important base cases are:

1. The search interval is empty, so the target is absent.

2. The middle element matches the target, so the index can be returned.

C Program: Recursive Binary Search

#include 

int binarySearchRecursive(
    const int arr[],
    int low,
    int high,
    int target
) {
    if (low > high) {
        return -1;
    }

    int mid = low + (high - low) / 2;

    if (arr[mid] == target) {
        return mid;
    }

    if (arr[mid] < target) {
        return binarySearchRecursive(
            arr, mid + 1, high, target
        );
    }

    return binarySearchRecursive(
        arr, low, mid - 1, target
    );
}

int main(void) {
    int arr[] = {10, 20, 30, 40, 50, 60, 70};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 50;

    int result = binarySearchRecursive(
        arr, 0, n - 1, target
    );

    if (result != -1) {
        printf("Element found at index %d\n", result);
    } else {
        printf("Element not found\n");
    }

    return 0;
}

Output:

Element found at index 4

Explanation of Recursive Binary Search

The function receives the array, the current lower and upper boundaries, and the target.

First, it checks whether low > high. If the interval is empty, it returns -1.

Otherwise, it calculates the middle index and compares the middle element with the target.

• If they match, the function returns the index.

• If the target is greater, the function calls itself on the right half.

• If the target is smaller, the function calls itself on the left half.

Each recursive call reduces the size of the remaining search interval, ensuring progress toward the base case.

Iterative vs Recursive Binary Search

Which Implementation Is Better?

For a simple binary search on an array, the iterative implementation is usually preferable when minimizing additional memory is important.

It has (O(1)) auxiliary space and avoids recursive function-call overhead.

The recursive version is useful for understanding recursion and expressing divide-and-conquer algorithms clearly. Its additional call-stack space is (O(\log n)) for binary search because the interval is approximately halved at each call.

Both approaches have (O(\log n)) worst-case time complexity.

4. Time Complexity Comparison

Time complexity describes how the number of computational steps grows as the input size increases.

For searching algorithms, complexity helps us understand how efficiently an algorithm can locate a target in a collection.

Linear Search Complexity

Binary Search Complexity

The average-case complexity depends on assumptions about the target's position and the input distribution. The table gives the standard asymptotic classifications for these algorithms.

Linear Search vs Binary Search

How to Choose the Right Searching Algorithm

Choose linear search when:

• The data is unsorted.

• The collection is small.

• Only a small number of searches will be performed.

• Sorting the data would create unnecessary overhead.

Choose binary search when:

• The data is already sorted.

• The collection is large.

• Fast repeated searching is important.

• The data structure supports efficient access to middle elements.

Remember that binary search's logarithmic complexity describes the search operation itself. If sorting is required first, the cost of sorting must also be considered.

Common Mistakes in Searching Algorithms

1. Using Binary Search on Unsorted Data

Binary search relies on the ordering of elements. Applying it to an unsorted array can produce incorrect results.

2. Incorrect Boundary Conditions

The iterative binary search loop should normally use low <= high. Using low < high without adjusting the algorithm can cause the final candidate to be skipped.

3. Incorrect Middle Index Updates

When searching the right half, update low to mid + 1. When searching the left half, update high to mid - 1.

Failing to exclude the already examined middle element can cause an infinite loop.

4. Forgetting the Recursive Base Case

Recursive binary search must stop when the search interval becomes empty. Without a correct base case, the function may continue calling itself indefinitely until the program runs out of stack space.

5. Confusing Index with Position

C array indices begin at zero. Therefore, index 3 represents the fourth element, not the third.

Conclusion

Searching algorithms are essential for finding information efficiently in arrays and other collections.

In this module, we learned:

• Linear search examines elements sequentially and works on sorted or unsorted arrays.

• Binary search repeatedly halves a search interval and requires sorted input.

• Iterative binary search uses loops and (O(1)) auxiliary space.

• Recursive binary search uses function calls and (O(\log n)) auxiliary stack space.

• Linear search has (O(n)) worst-case time complexity, while binary search has (O(\log n)) worst-case time complexity.

• The appropriate algorithm depends on the data organization, input size, and number of searches.

Understanding these algorithms prepares you for more advanced searching techniques and helps you select efficient solutions when building real-world applications.