/*
 * Name: Owen Sullivan
 * Date Submitted: 9/29/22
 * Lab Section: 006
 * Assignment Name: Lab 4: Searching and Sorting
 */

#ifndef SEARCHES_
#define SEARCHES_

#include <vector>

template <class T>
int linearSearch(std::vector<T> data, T target) {

    // Loop through elements in data vector
    for (int pos = 0; pos < data.size(); pos++) {

        // If value at current position is equal to target value,
        // return value
        if (data.at(pos) == target) {

            return pos;

        }

    }

    // If the function hasn't returned by this point,
    // the target doesn't exist in the data vector so
    // return -1
    return -1;

}

template <class T>
int binarySearch(std::vector<T> data, T target) {

    int lowIndex = 0;
    int midIndex;
    // Set highIndex to the size of the data vector, minus 1
    // since the first index is 0
    int highIndex = data.size() - 1;

    // Loop until lowIndex and highIndex are the same, indicating
    // there is no middle value left to check
    while (lowIndex != highIndex) {

        // Set midIndex equal to the midpoint between lowIndex and
        // highIndex
        midIndex = (lowIndex + highIndex) / 2;

        // If the value at midIndex is less than the target,
        // increment lowIndex
        if (data.at(midIndex) < target) {

            lowIndex++;

          // If the value at midIndex is greater than the target,
          // decrement highIndex
        } else if (data.at(midIndex) > target) {

            highIndex--;

          // If the value at midIndex is equal to the target,
          // return midIndex
        } else {

            return midIndex;

        }

    }

    // Evaluate midIndex again (for when the target
    // hasn't already been found)
    midIndex = (lowIndex + highIndex) / 2;

    // If the value at midIndex is equal to the target,
    // return midIndex
    if (data.at(midIndex) == target) {

        return midIndex;

      // Otherwise, return -1
    } else {

        return -1;

    }

}

#endif