Given a bitonic sequence arr[] 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 arr[].
• If the element is found then return the index otherwise return -1.
• You are expected to solve this problem in O(log n) time complexity.

Example 1

Input: arr[] = [-2, 5, 10, 20, 15, 4, 1], k = 10
Output: 2
Explanation: Element k Found at index 2

Example 2

Input: arr[] = [5, 6, 7, 18, 29, 20, 13, 8, 1], k = 30
Output: -1
Explanation: Element k not found in the array