Given a bitonic sequence of n distinct elements, write a program to search a given element k in the bitonic sequence.

Problem Note

  • A Bitonic Sequence is a sequence of numbers that is first strictly increasing then after a point strictly decreasing.
  • It is guaranteed that there are no duplicates in the input array.
  • If the element is found then return the index otherwise return -1.
  • You are expected to solve this problem in O(logn) time complexity.

Example 1

Input: A[] = [-3, 8, 9, 20, 17, 5, 1], k = 20
Output: 3 
Explanation: Element k Found at index 3

Example 2

Input: A[] = [5, 6, 7, 8, 9, 10, 3, 2, 1], k = 30
Output: -1