Searching Algorithms in C++

Introduction

Searching algorithms are fundamental to computer science and are used to retrieve information stored within some data structure. In this tutorial, we will explore two primary types of searching algorithms: linear search and binary search.

Linear Search

Linear search is the simplest searching algorithm. It checks each element in the list until it finds the target value or reaches the end of the list.

#include <iostream>
using namespace std;

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

int main() {
    int arr[] = {2, 4, 0, 1, 9};
    int x = 1;
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = linearSearch(arr, n, x);
    (result == -1) ? cout << "Element not found" 
                   : cout << "Element found at index " << result;
    return 0;
}
                

Binary Search

Binary search is a much faster search algorithm that works on sorted arrays. It repeatedly divides the search interval in half. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

#include <iostream>
using namespace std;

int binarySearch(int arr[], int l, int r, int x) {
    while (l <= r) {
        int m = l + (r - l) / 2;

        if (arr[m] == x)
            return m;

        if (arr[m] < x)
            l = m + 1;
        else
            r = m - 1;
    }
    return -1;
}

int main() {
    int arr[] = {2, 3, 4, 10, 40};
    int x = 10;
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = binarySearch(arr, 0, n-1, x);
    (result == -1) ? cout << "Element not found" 
                   : cout << "Element found at index " << result;
    return 0;
}
                

Comparison of Linear Search and Binary Search

Linear Search:

• Time Complexity: O(n)
• Works on both sorted and unsorted arrays

• Time Complexity: O(log n)
• Works only on sorted arrays

Conclusion

Searching algorithms are vital in computer science, providing methods to retrieve information from data structures. Linear search is simple but less efficient, while binary search is faster but requires sorted data. Understanding these algorithms is fundamental to developing efficient code.