Encuentra el punto bitónico en una secuencia bitónica dada

Se le da una secuencia bitónica, la tarea es encontrar el Punto Bitónico en ella. Una secuencia bitónica es una secuencia de números que primero es estrictamente creciente y luego después de un punto estrictamente decreciente.
Un punto bitónico es un punto en secuencia bitónica antes del cual los elementos son estrictamente crecientes y después del cual los elementos son estrictamente decrecientes. Un punto bitónico no existe si la array solo disminuye o solo aumenta.

Ejemplos: 

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

Una solución simple para este problema es utilizar la búsqueda lineal. El elemento arr[i] es un punto bitónico si ambos elementos i-1’th e i+1’th son menores que el i’th elemento. La complejidad del tiempo para este enfoque es O(n).

Una solución eficiente para este problema es utilizar la búsqueda binaria modificada .  Si arr[mid-1] < arr[mid] y arr[mid] > arr[mid+1] entonces hemos terminado con el punto bitónico.

• Si arr[mid] < arr[mid+1] entonces busque en el subconjunto derecho, de lo contrario busque en el subconjunto izquierdo.

Implementación:

// 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 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

# Python3 program to find bitonic
# point in a bitonic array.
 
# Function to find bitonic point
# using binary search
def 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] and 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 = [6, 7, 8, 11, 9, 5, 2, 1];
n = len(arr);
index = binarySearch(arr, 1, n-2);
if (index != -1):
        print(arr[index]);
 
# This code is contributed by mits

// 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 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
?>

<script>
 
// Javascript 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)
    {
        var mid = parseInt((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
var arr = [6, 7, 8, 11, 9, 5, 2, 1];
var n = arr.length;
var index = binarySearch(arr, 1, n - 2);
if (index != -1)
document.write( arr[index]);
 
 
// This code is contributed by Amit Katiyar
 
</script>

11

Complejidad de tiempo: O(Log n)
Espacio auxiliar: O(1), ya que no se requiere espacio adicional

Este artículo es una contribución de Shashank Mishra (Gullu) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.