## Search In Bitonic Array!

Given a bitonic sequence A of N distinct elements, write a program to find a given element B in the bitonic sequence in O(logN) time.

NOTE:

A Bitonic Sequence is a sequence of numbers which is first strictly increasing then after a point strictly decreasing.

Problem Constraints 3 <= N <= 10^5

1 <= A[i], B <= 10^8

Given array always contain a bitonic point.

Array A always contain distinct elements.

Input Format The first line given is an integer N, denoting the size of array A

The second line given is an integer array A denoting the bitonic sequence.

The third line given is an integer B.

Output Format Print a single integer denoting the position (0 index based) of the element B in the array A if B doesn’t exist in A return -1.

Example Input Input 1: 7 3 9 10 20 17 5 1 20

Input 2: 9 5 6 7 8 9 10 3 2 1 30

Example Output Output 1:

3 Output 2:

-1

Example Explanation Explanation 1:

B = 20 present in A at index 3 Explanation 2:

B = 30 is not present in A

## Solution:–

```import java.util.*;
import java.lang.*;
import java.io.*;

public class Main
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int arr[] = new int[n];

for(int i=0;i<n;i++)
{
arr[i]=sc.nextInt();
}
int b=sc.nextInt();

int index=-1;
for(int i=0;i<n;i++)
{
if(b==arr[i])
{
index=i;
}
}
System.out.print(index);
}
}```