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