Question
Bitonic Search
In a coding contest, Ava and Ben were discussing bitonic arrays, which Ava had just learned about in her DSA class. Ben challenged Ava to find a specific element in a bitonic array - a sequence that first increases and then decreases. Ava, with her sharp problem-solving skills, cracked the challenge in no time. Can you solve it? Given a bitonic array, print the index of the element (0-based indexing) if it’s present, or -1 if it’s not.
Input
The first line of the input contains two space-separated integers N and K, representing the size of an array and the element to be found.
The second line of the input contains N space-separated integers denoting the bitonic array A.
Constraints
3 ≤ N ≤ 105
-106 ≤ A[i], target ≤ 106
The second line of the input contains N space-separated integers denoting the bitonic array A.
Constraints
3 ≤ N ≤ 105
-106 ≤ A[i], target ≤ 106
Output
Print in a single line the index of the element (0- based) if present in the array else print -1.
Example
Sample Input
7 20
-3 9 18 20 17 5 1
Sample Output
3
Explanation
20 is present at index 3 in array A.
7 20
-3 9 18 20 17 5 1
Sample Output
3
Explanation
20 is present at index 3 in array A.