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