Searching 48

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]);
             
    }
}
 
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.