/* Problem:
 * https://practice.geeksforgeeks.org/problems/maximum-value-in-a-bitonic-array3001/1
 */

#include <iostream>
#include <vector>

int solution(const std::vector<int> &nums) {
  if (nums.size() == 0) {
    return -1;
  }
  if (nums.size() == 1) {
    return 0;
  };
  long long first = 0, last = nums.size() - 1, pi = last / 2;
  while (true) {
    if (pi == 0) {
      if (nums[pi] > nums[pi + 1]) {
        return pi;
      } else {
        first = pi + 1;
        pi = ((last - first) / 2) + first;
        continue;
      }
    } else if (pi == (long long)nums.size() - 1) {
      if (nums[pi] > nums[pi - 1]) {
        return pi;
      } else {
        last = pi - 1;
        pi = ((last - first) / 2) + first;
        continue;
      }
    }
    if (nums[pi] < nums[pi - 1]) {
      last = pi - 1;
    } else if (nums[pi] < nums[pi + 1]) {
      first = pi + 1;
    } else {
      return pi;
    }
    pi = ((last - first) / 2) + first;
  }

  return pi;
}

int main() {
  std::vector<int> nums1 = {1, 15, 25, 45, 42, 21, 17, 12, 11},
                   nums2 = {1, 45, 47, 50, 5};
  int i1, i2;
  i1 = solution(nums1);
  std::cout << i1 << " : " << nums1[i1] << '\n';
  i2 = solution(nums2);
  std::cout << i2 << " : " << nums2[i2] << '\n';
}