Searching Algorithms

Searching algorithms are algorithms designed to find the location or existence of a specific item (also known as a target or key) within a collection of data, such as an array or a list. These algorithms are like finding a particular book in a library or a specific name in a phone book.

There are various searching algorithms, but two commonly used ones are the “Linear Search” and the “Binary Search.” Let’s look at each of them:

1. Linear Search

Imagine you have a list of numbers or items, and you want to find a particular number in that list. The linear search algorithm works like this:

• Start from the beginning of the list and examine each element one by one.
• Compare the current element with the target number you want to find.
• If the current element matches the target number, you have found it! Return the position or index of the element.
• If the current element doesn’t match the target number, move on to the next element and repeat the comparison until you find the target number or reach the end of the list.

In C++, you can implement the linear search algorithm like this:

#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 where the target is found
        }
    }
    return -1; // Return -1 if the target is not found in the list
}

int main() {
    int arr[] = {10, 25, 8, 14, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 14;

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

    if (index != -1) {
        cout << "Target found at index: " << index << endl;
    } else {
        cout << "Target not found in the list." << endl;
    }

    return 0;
}

2. Binary Search

The binary search algorithm works only on a sorted list of items. It is much faster than the linear search for large lists. Here’s how it works:

• Start with the middle element of the sorted list.
• Compare the middle element with the target number.
• If the middle element is the target, you have found it! Return the position or index of the element.
• If the middle element is greater than the target, eliminate the right half of the list (since the target can only exist in the left half).
• If the middle element is less than the target, eliminate the left half of the list (since the target can only exist in the right half).
• Repeat the process by selecting the middle element of the remaining half and continue until you find the target or the list is empty.

In C++, you can implement the binary search algorithm like this:

#include <iostream>
using namespace std;

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

        if (arr[mid] == target) {
            return mid; // Return the index where the target is found
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return -1; // Return -1 if the target is not found in the list
}

int main() {
    int arr[] = {3, 8, 10, 14, 25};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 14;

    int index = binarySearch(arr, 0, n - 1, target);

    if (index != -1) {
        cout << "Target found at index: " << index << endl;
    } else {
        cout << "Target not found in the list." << endl;
    }

    return 0;
}

Remember, the binary search requires a sorted list. If the list is not sorted, you need to use the linear search algorithm.

Both searching algorithms have their advantages and are suitable for different scenarios. Linear search is useful for small lists or when the list is unsorted. Binary search is more efficient and ideal for large, sorted lists.