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 { //your code here 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); } }

## Add a Comment