C++ implementations of common search algorithms

Search Algorithms.cpp

//Author: Eshwary Mishra 2023

/**
 * This file will give implementations for common searching algorithms implemented in C++
 * 
 * For simplicity, we will use a vector for our lists. It should be noted that this can be copy
 * paste replaced for any list type that implements the [a] operator for finding an element at position
 * a and the internal element implements the <, >, and == operators. If either is not the case, then
 * the implementation must be modified.
 * 
 * Binary search - Splits the list into two until it is only left with the required value. It is good for large lists
 * Sequential search - Searches through the list linearly until it locates the required value. It is good for small lists
*/

#include <vector>

//We define a struct to better handle start and end indexes for searching lists with duplicate values
//where we prefer to retrieve ranges of values as opposed to just any instance of the value
struct indexes
{
    int first;
    int last;
};

/**
 * Binary searches a list of data. Binary search requires a sorted list.
 * This one does not handle duplicates and will return the first occurance of the value it finds
 * NOTE: This is not necessarly the first or last occurance of the value, just the first one it finds
 * 
 * O(log(n))
*/
static const int binary_search(const std::vector<int>& list, int value)
{
    int low = 0;
    int high = list.size() - 1;

    //Retrieve start index of target number
    int index = -1;
    while (low <= high)
    {
        const int mid = ((high - low) / 2) + low;

        if (list[mid] > value)
            //If the value is in the upper half, then we move the high up to the half way point
            high = mid - 1;
        else if (list[mid] == value)
        {
            //If we arrived at our number, then we are done
            index = mid;
            break;
        }
        else
            //If the value is in the lower half, then we move the low to the half way point
            low = mid + 1;
    }

    return index;
}

/**
 * Binary searches a list of data. Binary search requires a sorted list.
 * This one handles duplicates and will return the first and last occurance of the value
 * 
 * O(log(n))
 * NOTE: While effencify is the same as before, that does not mean it will be equally fast
*/
static const indexes binary_search_with_duplicates(const std::vector<int>& list, int value)
{
    int low = 0;
    int high = list.size() - 1;

    //Retrieve start index of target number
    int start_index = -1;
    while (low <= high)
    {
        const int mid = ((high - low) / 2) + low;

        if (list[mid] > value)
            //If the value is in the upper half, then we move the high up to the half way point
            high = mid - 1;
        else if (list[mid] == value)
        {
            //If we arrived at our number, then we set that as the start index and continue
            //the search normally until we arrive at the first iteration of our number
            //Notice here we set change high, not low. This is so we find the start index
            //by continuing the search on the top half of the array, not on the bottom half.
            start_index = mid;
            high = mid - 1;
        }
        else
            //If the value is in the lower half, then we move the low to the half way point
            low = mid + 1;
    }

    //Reset variables
    low = 0;
    high = list.size() - 1;

    //Retrieve end index of target number
    int end_index = -1;
    while (low <= high)
    {
        const int mid = ((high - low) / 2) + low;

        if (list[mid] > value)
            //If the value is in the upper half, then we move the high up to the half way point
            high = mid - 1;
        else if (list[mid] == value)
        {
            //If we arrived at our number, then we set that as the start index and continue 
            //the search normally until we arrive at the first iteration of our number.
            //Notice here we set change low, not high. This is so we find the end index
            //by continuing the search on the bottom half of the array, not on the top half.
            end_index = mid;
            low = mid + 1;
        }
        else
            //If the value is in the lower half, then we move the low to the half way point
            low = mid + 1;
    }

    return {start_index, end_index};
}

/**
 * Sequentally searches a list of data.
 * This does not handle duplicates. If there are any, it will return the first occurance
 * 
 * Best: O(1)
 * Average: O(n/2)
 * Worst: O(n)
*/
static const int sequential_search(const std::vector<int>& list, int value)
{
    //Iterate through every element until we find the value. When we find the value, we simply return an index to it
    for(int i = 0; i < list.size(); ++i)
    {
        if(list[i] == value)
            return i;
    }

    return -1;
}

/**
 * Sequentally searches a list of data.
 * This handles duplicates and will return indexes to all occurances of the value
 * 
 * O(n)
*/
static const std::vector<int> sequential_search_with_duplicates(const std::vector<int>& list, int value)
{
    std::vector<int> found_indexes;

    //Iterate through every element until we find the value. When we find the value, we simply return an index to it
    for(int i = 0; i < list.size(); ++i)
    {
        if(list[i] == value)
            found_indexes.push_back(i);
    }

    return found_indexes;
}

/**
 * Sequentally searches a sorted list of data. If data is sorted we can avoid always being O(n) since we can
 * stop at the first occurance of a different value. This handles duplicates and will return indexes to all
 * occurances of the value
 * 
 * k - number of times the value occurs in the list
 * Best: O(1 + k)
 * Average: O(n/2 + k)
 * Worst: O(n)
*/
static const std::vector<int> sequential_search_sorted_with_duplicates(const std::vector<int>& list, int value)
{
    std::vector<int> found_indexes;
    bool b_in_set_of_values = false;

    //Iterate through every element until we find the value. When we find the value, we simply return an index to it
    for(int i = 0; i < list.size(); ++i)
    {
        if(list[i] == value)
        {
            b_in_set_of_values = true;
            found_indexes.push_back(i);
        }
        else if (b_in_set_of_values)
            //This will run only on the first occurace of another value after we have recoreded all the indexes of our value
            break;
    }

    return found_indexes;
}

/**
 * Sequentally searches a sorted list of data. If data is sorted we can avoid always being O(n) since we can
 * stop at the first occurance of a different value. This handles duplicates and will return indexes to the
 * first and last occurances of the value
 * 
 * k - number of times the value occurs in the list
 * Best: O(1 + k)
 * Average: O(n/2 + k)
 * Worst: O(n)
*/
static const indexes sequential_search_sorted_with_duplicates_alternate(const std::vector<int>& list, int value)
{
    int first_index = -1;
    int last_index = -1;
    bool b_in_set_of_values = false;

    //Iterate through every element until we find the value. When we find the value, we simply return an index to it
    for(int i = 0; i < list.size(); ++i)
    {
        if(list[i] == value && !b_in_set_of_values)
        {
            b_in_set_of_values = true;
            first_index = i;
        }
        else if (b_in_set_of_values)
        {
            //This will run only on the first occurace of another value after we have recoreded all the indexes of our value
            last_index = i - 1;
            break;
        }
    }

    return {first_index, last_index};
}