Searching Algorithms

Searching Algorithms in C++

Searching refers to the process of finding a specific element in a collection of data, such as an array or a list. Searching algorithms are essential in various applications, such as looking up data in a database, finding elements in an array, or navigating through graphs. Below are the most common searching algorithms in C++.

Types of Searching Algorithms

1. Linear Search
2. Binary Search
3. Jump Search
4. Exponential Search
5. Interpolation Search

1. Linear Search

Linear Search is the simplest searching algorithm. It checks each element of the array sequentially from the beginning until the target element is found or the entire array has been searched.

Algorithm Overview:

• Start at the first element of the array.
• Check if the current element matches the target.
• If found, return the index of the element; otherwise, move to the next element.
• Continue until either the element is found or the array ends.

Time Complexity:

• Worst Case: O(n) (if the element is at the end or not present at all)
• Best Case: O(1) (if the element is at the beginning)
• Average Case: O(n)

Code Example:

#include <iostream>
using namespace std;

int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i;  // Return the index if found
        }
    }
    return -1;  // Return -1 if element is not found
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 22;

    int result = linearSearch(arr, n, target);
    if (result != -1) {
        cout << "Element found at index: " << result << endl;
    } else {
        cout << "Element not found" << endl;
    }

    return 0;
}

Output:

Element found at index: 3

2. Binary Search

Binary Search is a more efficient algorithm for finding an element in a sorted array. It repeatedly divides the search interval in half and compares the target with the middle element.

Algorithm Overview:

• Begin with two pointers, one at the beginning (low) and one at the end (high) of the array.
• Find the middle element and compare it with the target:
  • If the middle element is the target, return the index.
  • If the target is smaller, search in the left half by adjusting the high pointer.
  • If the target is larger, search in the right half by adjusting the low pointer.
• Repeat the process until the element is found or the search interval is empty.

Time Complexity:

• Worst Case: O(log n)
• Best Case: O(1) (if the element is at the middle)
• Average Case: O(log n)

Code Example:

#include <iostream>
using namespace std;

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

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

        if (arr[mid] == target) {
            return mid;  // Element found
        }
        else if (arr[mid] < target) {
            low = mid + 1;  // Search in the right half
        }
        else {
            high = mid - 1;  // Search in the left half
        }
    }

    return -1;  // Element not found
}

int main() {
    int arr[] = {11, 12, 22, 25, 64};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 22;

    int result = binarySearch(arr, n, target);
    if (result != -1) {
        cout << "Element found at index: " << result << endl;
    } else {
        cout << "Element not found" << endl;
    }

    return 0;
}

Output:

Element found at index: 2

3. Jump Search

Jump Search is an algorithm that works on sorted arrays. It works by jumping ahead by a fixed block size and then performing a linear search within the block where the target element might lie. This reduces the number of comparisons compared to linear search.

Algorithm Overview:

• Find the block size, which is the square root of the array size.
• Jump ahead by the block size, comparing the target with the element at each step.
• Once the target is between two blocks, perform a linear search within that block.

Time Complexity:

• Worst Case: O(√n)
• Best Case: O(1)
• Average Case: O(√n)

Code Example:

#include <iostream>
#include <cmath>
using namespace std;

int jumpSearch(int arr[], int n, int target) {
    int step = sqrt(n);  // Calculate block size
    int prev = 0;

    // Jump ahead by step until we reach an element greater than the target or end of the array
    while (arr[min(step, n) - 1] < target) {
        prev = step;
        step += sqrt(n);
        if (prev >= n) {
            return -1;
        }
    }

    // Perform linear search within the block
    for (int i = prev; i < min(step, n); i++) {
        if (arr[i] == target) {
            return i;
        }
    }

    return -1;  // Element not found
}

int main() {
    int arr[] = {1, 4, 7, 12, 16, 19, 23, 29, 31, 35};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 19;

    int result = jumpSearch(arr, n, target);
    if (result != -1) {
        cout << "Element found at index: " << result << endl;
    } else {
        cout << "Element not found" << endl;
    }

    return 0;
}

Output:

Element found at index: 5

4. Exponential Search

Exponential Search is an extension of binary search. It is used for searching in sorted arrays, where it first finds the range where the element could exist by doubling the size of the range until the element is less than the current value.

Algorithm Overview:

• Start with an index i = 1, and double the index value (i.e., i = 2, 4, 8, 16, ...) until the target is less than the element at the current index.
• Once the range is found, perform a binary search within the range.

Time Complexity:

• Worst Case: O(log n)
• Best Case: O(1) (if the element is at the first index)
• Average Case: O(log n)

Code Example:

#include <iostream>
#include <cmath>
using namespace std;

int binarySearch(int arr[], int left, int right, int target) {
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target)
            return mid;
        if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return -1;
}

int exponentialSearch(int arr[], int n, int target) {
    if (arr[0] == target) return 0;

    int i = 1;
    while (i < n && arr[i] <= target) {
        i *= 2;
    }

    return binarySearch(arr, i / 2, min(i, n - 1), target);
}

int main() {
    int arr[] = {1, 4, 7, 12, 16, 19, 23, 29, 31, 35};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 19;

    int result = exponentialSearch(arr, n, target);
    if (result != -1) {
        cout << "Element found at index: " << result << endl;
    } else {
        cout << "Element not found" << endl;
    }

    return 0;
}

Output:

Element found at index: 5

5. Interpolation Search

Interpolation Search is an improvement over binary search for uniformly distributed values. Instead of dividing the range in half, it estimates the position of the target value using a formula based on the values at the low and high indices.

Algorithm Overview:

• Estimate the position of the target using the formula: $$pos = low + \left( \frac{(target - arr[low]) \times (high - low)}{arr[high] - arr[low]} \right)$$
• If the target is found, return the index; otherwise, adjust the search range.

Time Complexity:

• Worst Case: O(n) (if the data is not uniformly