Tutorialspoint.dev

Find bitonic point in given bitonic sequence

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.

A Bitonic Point is a point in bitonic sequence before which elements are strictly increasing and after which elements are strictly decreasing. A Bitonic point doesn’t exist if array is only decreasing or only increasing.

Examples :



Input : arr[] = {6, 7, 8, 11, 9, 5, 2, 1}
Output: 11
All elements before 11 are smaller and all
elements after 11 are greater.

Input : arr[] = {-3, -2, 4, 6, 10, 8, 7, 1}
Output: 10


A simple solution for this problem is to use linear search. Element arr[i] is bitonic point if both i-1’th and i+1’th both elements are less than i’th element. Time complexity for this approach is O(n).

An efficient solution for this problem is to use modified binary search.

  • If arr[mid-1] < arr[mid] and arr[mid] > arr[mid+1] then we are done with bitonic point.
  • If arr[mid] < arr[mid+1] then search in right sub-array, else search in left sub-array.

C++

// C++ program to find bitonic point in a bitonic array.
#include<bits/stdc++.h>
using namespace std;
  
// Function to find bitonic point using binary search
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 to run the case
int main()
{
    int arr[] = {6, 7, 8, 11, 9, 5, 2, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    int index = binarySearch(arr, 1, n-2);
    if (index != -1)
       cout << arr[index];
    return 0;
}

Java

// Java program to find bitonic
// point in a bitonic array.
  
import java.io.*;
  
class GFG 
{
    // 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) 
    {
        int arr[] = {6, 7, 8, 11, 9, 5, 2, 1};
        int n = arr.length;
        int index = binarySearch(arr, 1, n - 2);
        if (index != -1)
        System.out.println ( arr[index]);
              
    }
}
  
// This code is contributed by vt_m

C#

// C# program to find bitonic
// point in a bitonic array.
using System;
  
class GFG 
{
    // 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 () 
    {
        int []arr = {6, 7, 8, 11, 9, 5, 2, 1};
        int n = arr.Length;
        int index = binarySearch(arr, 1, n - 2);
        if (index != -1)
        Console.Write ( arr[index]);
    }
}
  
// This code is contributed by nitin mittal

PHP

<?php
// PHP program to find bitonic 
// point in a bitonic array.
  
// Function to find bitonic point 
// using binary search
function binarySearch($arr, $left, $right)
{
    if ($left <= $right)
    {
        $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 Code
    $arr = array(6, 7, 8, 11, 9, 5, 2, 1);
    $n = sizeof($arr);
    $index = binarySearch($arr, 1, $n-2);
    if ($index != -1)
        echo $arr[$index];
  
// This code is contributed by nitin mittal
?>


Output:

11

Time complexity : O(Log n)

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter