Introduction to Searching Algorithms

Searching Algorithms in C is the process of finding a particular element in a collection of data. In C, various searching techniques are available to locate data efficiently in arrays or other data structures. These algorithms are classified into linear and non-linear methods based on how they traverse the data.

Searching is crucial in real-world applications like databases, file systems, and data retrieval systems. Understanding these techniques allows you to choose the best method depending on the size and structure of your data.

Types of Searching Algorithms

1. Linear Search

Definition:

Linear Searching Algorithms in C is the simplest searching technique that checks each element in the array one by one until the desired element is found or the array ends. It does not require the array to be sorted.

When to Use:

• When the array is unsorted.
• When the dataset is small.

Algorithm:

1. Start from the first element of the array.
2. Compare the current element with the target key.
3. If it matches, return the index.
4. If it doesn’t, move to the next element.
5. If the end of the array is reached and no match is found, return -1.

C Program for Linear Search: Click me!

#include <stdio.h>

int linearSearch(int arr[], int size, int key) {
    for(int i = 0; i < size; i++) {
        if(arr[i] == key)
            return i;
    }
    return -1;
}

int main() {
    int arr[] = {34, 78, 12, 45, 89};
    int key = 45;
    int result = linearSearch(arr, 5, key);

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

    return 0;
}

Advantages:

• Simple to implement.
• Works on both sorted and unsorted arrays.
• No additional data structure needed.

Disadvantages:

• Inefficient for large datasets.
• Time-consuming as every element is checked.

2. Binary Search

Definition:

Binary Searching Algorithms in C is a faster searching algorithm that only works on sorted arrays. It repeatedly divides the search range in half, comparing the middle element with the target value.

When to Use:

• When the array is sorted.
• When fast lookup is required on large datasets.

Algorithm:

1. Set two pointers: low = 0 and high = size - 1.
2. Repeat while low <= high:
   • Calculate the middle index: mid = (low + high) / 2.
   • If arr[mid] equals the key, return mid.
   • If the key is less than arr[mid], search in the left half by setting high = mid - 1.
   • If the key is greater than arr[mid], search in the right half by setting low = mid + 1.
3. If no match is found, return -1.

C Program for Binary Search: Click me!

#include <stdio.h>

int binarySearch(int arr[], int size, int key) {
    int low = 0, high = size - 1;

    while(low <= high) {
        int mid = (low + high) / 2;

        if(arr[mid] == key)
            return mid;
        else if(arr[mid] < key)
            low = mid + 1;
        else
            high = mid - 1;
    }

    return -1;
}

int main() {
    int arr[] = {10, 20, 30, 40, 50, 60};
    int key = 40;
    int result = binarySearch(arr, 6, key);

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

    return 0;
}

Advantages:

• Faster than linear search.
• Efficient for large sorted datasets.
• Reduces the number of comparisons.

Disadvantages:

• Only works on sorted arrays.
• Requires additional logic for maintaining sorted data.

3. Interpolation Search

Definition:

Interpolation Searching Algorithms in C is an improvement over Binary Search. It estimates the probable location of the target based on its value and the values at the boundaries. It is most efficient when the data is evenly distributed.

When to Use:

• When the array is sorted and values are uniformly distributed.
• When average case performance is preferred over worst case.

Algorithm:

1. Initialize low = 0, high = size - 1.
2. While low <= high and the key lies between arr[low] and arr[high]:
   • Estimate the position using: iniCopyEditpos = low + ((key - arr[low]) * (high - low)) / (arr[high] - arr[low])
   • If arr[pos] == key, return pos.
   • If arr[pos] < key, update low = pos + 1.
   • If arr[pos] > key, update high = pos - 1.
3. If key not found, return -1.

C Program for Interpolation Search: Click me!

#include <stdio.h>

int interpolationSearch(int arr[], int size, int key) {
    int low = 0, high = size - 1;

    while(low <= high && key >= arr[low] && key <= arr[high]) {
        int pos = low + ((key - arr[low]) * (high - low)) / 
                  (arr[high] - arr[low]);

        if(arr[pos] == key)
            return pos;
        else if(arr[pos] < key)
            low = pos + 1;
        else
            high = pos - 1;
    }

    return -1;
}

int main() {
    int arr[] = {10, 20, 30, 40, 50, 60, 70};
    int key = 60;
    int result = interpolationSearch(arr, 7, key);

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

    return 0;
}

Advantages:

• More efficient than binary search for uniformly distributed data.
• Reduces search time significantly for suitable data.

Disadvantages:

• Works only on sorted and uniformly distributed arrays.
• Performance degrades on non-uniform data.

Comparison Table

Complete Working Example of Searching Algorithms in C : Click me!

#include <stdio.h>

int linearSearch(int arr[], int size, int key) {
    for(int i = 0; i < size; i++) {
        if(arr[i] == key)
            return i;
    }
    return -1;
}

int binarySearch(int arr[], int size, int key) {
    int low = 0, high = size - 1;
    while(low <= high) {
        int mid = (low + high) / 2;

        if(arr[mid] == key)
            return mid;
        else if(arr[mid] < key)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return -1;
}

int interpolationSearch(int arr[], int size, int key) {
    int low = 0, high = size - 1;
    while(low <= high && key >= arr[low] && key <= arr[high]) {
        int pos = low + ((key - arr[low]) * (high - low)) /
                  (arr[high] - arr[low]);

        if(arr[pos] == key)
            return pos;
        else if(arr[pos] < key)
            low = pos + 1;
        else
            high = pos - 1;
    }
    return -1;
}

int main() {
    int arr[] = {10, 20, 30, 40, 50, 60};
    int key = 40;

    printf("Linear Search:\n");
    int res1 = linearSearch(arr, 6, key);
    (res1 != -1) ? printf("Found at index %d\n", res1) : printf("Not found\n");

    printf("Binary Search:\n");
    int res2 = binarySearch(arr, 6, key);
    (res2 != -1) ? printf("Found at index %d\n", res2) : printf("Not found\n");

    printf("Interpolation Search:\n");
    int res3 = interpolationSearch(arr, 6, key);
    (res3 != -1) ? printf("Found at index %d\n", res3) : printf("Not found\n");

    return 0;
}

Applications of Searching Algorithms in C

• Searching in databases and file systems
• Auto-complete features in applications
• Search engines and online shopping filters
• Spell-checking and text analysis
• User authentication and access control

Conclusion

Searching Algorithms in C are essential tools for efficiently locating elements in data structures.

• Use Linear Search for small or unsorted datasets.
• Prefer Binary Search for sorted data when speed is crucial.
• Choose Interpolation Search when data is sorted and uniformly distributed.

A strong understanding of these techniques helps in solving real-world problems more effectively in system design and software applications.

Interview Questions

1. What is the difference between Linear Search and Binary Search?

Company: Infosys
Answer:

• Linear Search checks every element one by one, while Binary Search divides the array and checks the middle element.
• Linear Search works on unsorted arrays, Binary Search requires a sorted array.
• Linear Search has O(n) time, Binary Search has O(log n) time.

2. When should you prefer Linear Search over Binary Searching Algorithms in C?

Company: TCS
Answer:

• Use Linear Search when the array is unsorted or very small.
• It is also helpful when you only need to find the first occurrence of an item.
• It’s simple and doesn’t need any special conditions.

3. What is the advantage of Binary Search?

Company: Accenture
Answer:

• Binary Search is faster than Linear Search for large, sorted arrays.
• It reduces the number of comparisons by dividing the array in half each time, giving a time complexity of O(log n).

4. What happens if we apply Binary Search on an unsorted array?

Company: Wipro
Answer:

• It will not work correctly and may return wrong results, because Binary Search assumes that the array is already sorted.
• Always sort the array before using Binary Search.

5. Is Binary Search recursive or iterative? Which one is better?

Company: IBM
Answer:

• Binary Search can be written using recursion or iteration.
• Both methods work the same, but iterative Binary Search is generally more efficient in C because it avoids function call overhead.

Quizzes

Searching Algorithms in C Quiz

Start Quiz

Question

Your answer:

Correct answer:

Next

You got {{SCORE_CORRECT}} out of {{SCORE_TOTAL}}

Your Answers