QUESTION
You are given a bitonic sequence, the task is to find Bitonic Point in it. A Bitonic Sequence is a sequence of numbers which is first strictly increasing then after a point strictly decreasing.\nA Bitonic Point is a point in bitonic sequence before which elements are strictly increasing and after which elements are strictly decreasing. A Bitonic point doesnt exist if array is only decreasing or only increasing.\nInput \nThe number of elements in the bitonic sequence and the sequence. \n.
“TESTCASE_1”: “8\n6 7 8 11 9 5 2 1\n###—###SEPERATOR—###—\n11”, “TESTCASE_2”: “8\n-3 -2 4 6 10 8 7 1\n###—###SEPERATOR—###—\n10”, “TESTCASE_3”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0
ANSWER
import java.io.*;
// Java program to find bitonic
// point in a bitonic array.
import java.util.*;
class TestClass
{
// Function to find bitonic point
// using binary search
static int binarySearch(int arr[], int left,
int right)
{
if (left <= right)
{
int mid = (left + right) / 2;
// base condition to check if arr[mid]
// is bitonic point or not
if (arr[mid - 1] < arr[mid] &&
arr[mid] > arr[mid + 1])
return mid;
// We assume that sequence is bitonic. We go to
// right subarray if middle point is part of
// increasing subsequence. Else we go to left
// subarray.
if (arr[mid] < arr[mid + 1])
return binarySearch(arr, mid + 1, right);
else
return binarySearch(arr, left, mid - 1);
}
return -1;
}
// Driver program
public static void main (String[] args)
{
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 index = binarySearch(arr, 1, n - 2);
if (index != -1)
System.out.println ( arr[index]);
}
}