Searching

Searching refers to the process of finding a specific value or element within a collection of data, such as an array, a list, or a tree. The goal of searching is to determine whether or not the value is present in the data structure, and if so, to locate the position or node where it occurs.

Linear Search

Linear search is a simple searching algorithm that searches for an element in a given array or list by iterating through each element one by one until it finds the target element. Here's an explanation of linear search with an example C++ implementation:

Linear Search Algorithm

Start with the first element of the array.

Compare the current element with the target element.

If the target element is found, return the index of the element.

If the target element is not found, move to the next element in the array and repeat the process.

If the entire array is traversed and the target element is not found, return -1 to indicate that the element was not found.

C++ Implementation


#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 -1;
}

int main() {
    int arr[] = {1, 5, 2, 7, 6, 8, 4};
    int n = sizeof(arr)/sizeof(arr[0]);
    int target = 7;
    int index = linearSearch(arr, n, target);
    if (index != -1) {
        cout << "Element found at index " << index << endl;
    }
    else {
        cout << "Element not found" << endl;
    }
    return 0;
}

This implementation defines a function linearSearch that takes an integer array arr, the size of the array n, and the target element target. It then iterates through each element of the array, checking if it matches the target element. If a match is found, it returns the index of the element. If no match is found after iterating through the entire array, it returns -1 to indicate that the element was not found.

Overall, the time complexity of linear search is O(n), where n is the size of the array. It's a simple search algorithm that is easy to implement but may not be efficient for larger arrays with many elements.

Sentinel Search

Sentinel search is a searching algorithm that is an optimized version of linear search. It works by adding a special element, called a sentinel, to the end of the input array, which eliminates the need for bounds checking during the search process. Here's an explanation of sentinel search with an example C++ implementation:

Sentinel Search Algorithm

Add the target element to the end of the input array and store its index.

Start with the first element of the array and compare it with the target element.

If the current element matches the target element, return its index.

If the current element does not match the target element, move to the next element in the array and repeat the process.

Repeat step 4 until the sentinel element is reached.

If the sentinel element is reached and the target element is not found, return -1 to indicate that the element was not found.

C++ Implementation


#include <iostream>
using namespace std;

int sentinelSearch(int arr[], int n, int target) {
    int last = arr[n-1];
    arr[n-1] = target;
    int i = 0;
    while (arr[i] != target) {
        i++;
    }
    arr[n-1] = last;
    if (i < n-1 || arr[n-1] == target) {
        return i;
    }
    else {
        return -1;
    }
}

int main() {
    int arr[] = {1, 5, 2, 7, 6, 8, 4};
    int n = sizeof(arr)/sizeof(arr[0]);
    int target = 7;
    int index = sentinelSearch(arr, n, target);
    if (index != -1) {
        cout << "Element found at index " << index << endl;
    }
    else {
        cout << "Element not found" << endl;
    }
    return 0;
}

This implementation defines a function sentinelSearch that takes an integer array arr, the size of the array n, and the target element target. It then adds the target element to the end of the input array and stores its index. The function then iterates through each element of the array, comparing it with the target element. If a match is found, it returns the index of the element. If the sentinel element is reached and the target element is not found, it returns -1 to indicate that the element was not found.

Overall, the time complexity of sentinel search is O(n), where n is the size of the array. However, it's more efficient than linear search in practice, as it eliminates the need for bounds checking during the search process.

Binary Search

Binary search is a searching algorithm that works on a sorted array or list by repeatedly dividing the search interval in half until the target element is found, or until the interval is empty. Here's an explanation of binary search with an example C++ implementation:

Binary Search Algorithm

Start with the entire sorted array or list.

Compare the middle element of the array or list with the target element.

If the middle element matches the target element, return the index of the element.

If the middle element is less than the target element, search the right half of the array and repeat from step 2.

If the middle element is greater than the target element, search the left half of the array and repeat from step 2.

If the target element is not found after the entire array is searched, return -1 to indicate that the element was not found.

C++ Implementation


#include <iostream>
using namespace std;

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

int main() {
    int arr[] = {1, 2, 4, 5, 6, 7, 8};
    int n = sizeof(arr)/sizeof(arr[0]);
    int target = 5;
    int index = binarySearch(arr, n, target);
    if (index != -1) {
        cout << "Element found at index " << index << endl;
    }
    else {
        cout << "Element not found" << endl;
    }
    return 0;
}

This implementation defines a function binarySearch that takes an integer array arr, the size of the array n, and the target element target. It then initializes two variables left and right that represent the range of the search interval. The function then repeatedly computes the middle index of the search interval and compares the middle element with the target element. If the middle element matches the target element, it returns the index of the element. If the middle element is less than the target element, it searches the right half of the array. If the middle element is greater than the target element, it searches the left half of the array. The function repeats this process until the target element is found or the search interval is empty.

Overall, the time complexity of binary search is O(logn), where n is the size of the array. It's a more efficient search algorithm than linear search for larger arrays, as it reduces the search interval by half at each iteration.

Fibonacci Search

Fibonacci search is a searching algorithm that works by dividing the array into two parts that have sizes that are consecutive Fibonacci numbers. Here's an explanation of Fibonacci search with an example C++ implementation:

Fibonacci Search Algorithm

Initialize two Fibonacci numbers fibM and fibM1 that are the smallest Fibonacci numbers greater than or equal to the size of the array.

While fibM > 1, compare the element that is min(i + fibM1, n-1) with the target element.

If the middle element matches the target element, return its index.

If the middle element is less than the target element, move the two Fibonacci numbers down one position and search in the lower part of the array.

If the middle element is greater than the target element, move the two Fibonacci numbers down two positions and search in the upper part of the array.

If the target element is not found after the entire array is searched, return -1 to indicate that the element was not found.

C++ Implementation


#include <iostream>
using namespace std;

int fibonacciSearch(int arr[], int n, int target) {
    int fibM = 1;
    int fibM1 = 0;
    int fibM2 = 0;
    while (fibM < n) {
        fibM2 = fibM1;
        fibM1 = fibM;
        fibM = fibM1 + fibM2;
    }
    int i = -1;
    while (fibM > 1) {
        int j = min(i + fibM2, n-1);
        if (arr[j] < target) {
            fibM = fibM1;
            fibM1 = fibM2;
            fibM2 = fibM - fibM1;
            i = j;
        }
        else if (arr[j] > target) {
            fibM = fibM2;
            fibM1 = fibM1 - fibM2;
            fibM2 = fibM - fibM1;
        }
        else {
            return j;
        }
    }
    if (fibM1 && arr[i+1] == target) {
        return i + 1;
    }
    return -1;
}

int main() {
    int arr[] = {1, 2, 4, 5, 6, 7, 8};
    int n = sizeof(arr)/sizeof(arr[0]);
    int target = 5;
    int index = fibonacciSearch(arr, n, target);
    if (index != -1) {
        cout << "Element found at index " << index << endl;
    }
    else {
        cout << "Element not found" << endl;
    }
    return 0;
}

This implementation defines a function fibonacciSearch that takes an integer array arr, the size of the array n, and the target element target. It then initializes two Fibonacci numbers fibM and fibM1 that are the smallest Fibonacci numbers greater than or equal to the size of the array. The function then iteratively searches the array by checking elements separated by fibM1 and fibM2 indices. If a match is found, it returns the index of the element. If the target element is not found after the entire array is searched, it returns -1 to indicate that the element was not found.

Overall, the time complexity of Fibonacci search is O(logn), where n is the size of the array. It's more efficient than binary search for larger arrays that have non-uniformly distributed elements.

PRACTICE PROBLEMS :

First Bad Version

Guess Number Higher or Lower