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

using namespace std;

int iterativeBinarySearch(const vector<int> &arr, int target) {
  int left = 0;
  int right = arr.size() - 1;

  while (left <= right) {
    int mid = left + (right - left) / 2;

    if (arr[mid] == target) {
      return mid;
    }
    if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return -1;
}

int recursiveBinarySearch(const vector<int> &arr, int target, int left,
                          int right) {
  if (left <= right) {
    int mid = left + (right - left) / 2;

    if (arr[mid] == target) {
      return mid;
    }
    if (arr[mid] < target) {
      return recursiveBinarySearch(arr, target, mid + 1, right);
    } else {
      return recursiveBinarySearch(arr, target, left, mid - 1);
    }
  }
  return -1;
}

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

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

  auto startRec = chrono::high_resolution_clock::now();
  int recResult = recursiveBinarySearch(array, target, 0, array.size() - 1);
  auto endRec = chrono::high_resolution_clock::now();
  chrono::duration<double> recTime = endRec - startRec;

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

  return 0;
}