#include <chrono>
#include <iostream>
#include <vector>

using namespace std;

int iterativeSearch(const vector<int> &arr, int target) {
  for (size_t i = 0; i < arr.size(); ++i) {
    if (arr[i] == target) {
      return i;
    }
  }
  return -1;
}

int recursiveSearch(const vector<int> &arr, int target, size_t index = 0) {
  if (index >= arr.size()) {
    return -1;
  }
  if (arr[index] == target) {
    return index;
  }
  return recursiveSearch(arr, target, index + 1);
}

int main() {
  vector<int> array = {2, 3, 4, 10, 40};
  int target = 10;

  auto startIter = chrono::high_resolution_clock::now();
  int iterResult = iterativeSearch(array, target);
  auto endIter = chrono::high_resolution_clock::now();
  chrono::duration<double> iterTime = endIter - startIter;

  auto startRec = chrono::high_resolution_clock::now();
  int recResult = recursiveSearch(array, target);
  auto endRec = chrono::high_resolution_clock::now();
  chrono::duration<double> recTime = endRec - startRec;

  cout << "Iterative search result: Index " << iterResult
       << ", Time taken: " << iterTime.count() << " seconds\n";
  cout << "Recursive search result: Index " << recResult
       << ", Time taken: " << recTime.count() << " seconds\n";

  return 0;
}