Mínimo en una array que primero disminuye y luego aumenta

Dada una array de N enteros donde los elementos de la array forman una secuencia estrictamente decreciente y creciente. La tarea es encontrar el número más pequeño en tal array. 
Restricciones : N >= 3 
Ejemplos: 
 

Input: a[] = {2, 1, 2, 3, 4}
Output: 1

Input: a[] = {8, 5, 4, 3, 4, 10}
Output: 3 

Un enfoque ingenuo es atravesar linealmente la array y encontrar el número más pequeño. Complejidad de tiempo: O (N), necesitamos usar un bucle para atravesar N veces linealmente. 

Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.
Un enfoque eficiente es modificar la búsqueda binaria y usarla. Divida la array en dos mitades, use la búsqueda binaria para verificar si a[mid] <a[mid+1] o no. Si a[mid] < a[mid+1] , entonces el número más pequeño se encuentra en la primera mitad, que es de bajo a medio , de lo contrario, se encuentra en la segunda mitad, que es de medio+1 a alto . 
Algoritmo: 
 

while(lo > 1

    if a[mid] < a[mid+1] then hi = mid

    else lo = mid+1
} 

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ program to find the smallest number
// in an array of decrease and increasing numbers
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the smallest number's index
int minimal(int a[], int n)
{
    int lo = 0, hi = n - 1;
 
    // Do a binary search
    while (lo < hi) {
 
        // Find the mid element
        int mid = (lo + hi) >> 1;
 
        // Check for break point
        if (a[mid] < a[mid + 1]) {
            hi = mid;
        }
        else {
            lo = mid + 1;
        }
    }
 
    // Return the index
    return lo;
}
 
// Driver Code
int main()
{
    int a[] = { 8, 5, 4, 3, 4, 10 };
    int n = sizeof(a) / sizeof(a[0]);
    int ind = minimal(a, n);
 
    // Print the smallest number
    cout << a[ind];
}

// Java program to find the smallest number
// in an array of decrease and increasing numbers
class Solution
{
// Function to find the smallest number's index
static int minimal(int a[], int n)
{
    int lo = 0, hi = n - 1;
 
    // Do a binary search
    while (lo < hi) {
 
        // Find the mid element
        int mid = (lo + hi) >> 1;
 
        // Check for break point
        if (a[mid] < a[mid + 1]) {
            hi = mid;
        }
        else {
            lo = mid + 1;
        }
    }
 
    // Return the index
    return lo;
}
 
// Driver Code
public static void main(String args[])
{
    int a[] = { 8, 5, 4, 3, 4, 10 };
    int n = a.length;
    int ind = minimal(a, n);
 
    // Print the smallest number
    System.out.println( a[ind]);
}
}
//contributed by Arnab Kundu

# Python 3 program to find the smallest
# number in a array of decrease and
# increasing numbers
 
# function to find the smallest
# number's index
def minimal(a, n):
     
    lo, hi = 0, n - 1
     
    # Do a binary search
    while lo < hi:
         
        # find the mid element
        mid = (lo + hi) // 2
         
        # Check for break point
        if a[mid] < a[mid + 1]:
            hi = mid
        else:
            lo = mid + 1
        return lo
     
# Driver code
a = [8, 5, 4, 3, 4, 10]
 
n = len(a)
 
ind = minimal(a, n)
 
# print the smallest number
print(a[ind])
 
# This code is contributed
# by Mohit Kumar

// C# program to find the smallest number
// in an array of decrease and increasing numbers
using System;
class Solution
{
// Function to find the smallest number's index
static int minimal(int[] a, int n)
{
    int lo = 0, hi = n - 1;
 
    // Do a binary search
    while (lo < hi) {
 
        // Find the mid element
        int mid = (lo + hi) >> 1;
 
        // Check for break point
        if (a[mid] < a[mid + 1]) {
            hi = mid;
        }
        else {
            lo = mid + 1;
        }
    }
 
    // Return the index
    return lo;
}
 
// Driver Code
public static void Main()
{
    int[] a = { 8, 5, 4, 3, 4, 10 };
    int n = a.Length;
    int ind = minimal(a, n);
 
    // Print the smallest number
    Console.WriteLine( a[ind]);
}
}
//contributed by Mukul singh

<?php
// PHP program to find the smallest number
// in an array of decrease and increasing numbers
 
// Function to find the smallest
// number's index
function minimal($a, $n)
{
    $lo = 0;
    $hi = $n - 1;
 
    // Do a binary search
    while ($lo < $hi)
    {
 
        // Find the mid element
        $mid = ($lo + $hi) >> 1;
 
        // Check for break point
        if ($a[$mid] < $a[$mid + 1])
        {
            $hi = $mid;
        }
        else
        {
            $lo = $mid + 1;
        }
    }
 
    // Return the index
    return $lo;
}
 
// Driver Code
$a = array( 8, 5, 4, 3, 4, 10 );
$n = sizeof($a);
$ind = minimal($a, $n);
 
// Print the smallest number
echo $a[$ind];
 
// This code is contributed
// by Sach_Code
?>

<script>
 
    // Javascript program to find the smallest number
    // in an array of decrease and increasing numbers
     
    // Function to find the smallest number's index
    function minimal(a, n)
    {
        let lo = 0, hi = n - 1;
       
        // Do a binary search
        while (lo < hi) {
       
            // Find the mid element
            let mid = (lo + hi) >> 1;
       
            // Check for break point
            if (a[mid] < a[mid + 1]) {
                hi = mid;
            }
            else {
                lo = mid + 1;
            }
        }
       
        // Return the index
        return lo;
    }
     
    let a = [ 8, 5, 4, 3, 4, 10 ];
    let n = a.length;
    let ind = minimal(a, n);
   
    // Print the smallest number
    document.write(a[ind]);
     
</script>

3

Complejidad de tiempo : O (Log N), como estamos usando búsqueda binaria, en búsqueda binaria en cada recorrido reducimos por división de 2 por lo que el tiempo efectivo será 1+1/2+1/4+… que es equivalente a logN .
Espacio auxiliar : O(1), ya que no estamos utilizando ningún espacio adicional.