Dada una array ordenada arr[] de distintos elementos que se gira en algún punto desconocido, la tarea es encontrar el máximo de elementos en ella.
Ejemplos:
Entrada: arr[] = {3, 4, 5, 1, 2}
Salida: 5
Entrada: arr[] = {1, 2, 3}
Salida: 3
Enfoque: una solución simple es atravesar la array completa y encontrar el máximo. Esta solución requiere tiempo O(n).
Podemos hacerlo en O (Inicio de sesión) usando Búsqueda binaria. Si observamos más de cerca los ejemplos anteriores, podemos descubrir fácilmente el siguiente patrón:
- El elemento máximo es el único elemento cuyo siguiente es menor que él. Si no hay el siguiente elemento más pequeño, entonces no hay rotación (el último elemento es el máximo). Verificamos esta condición para el elemento medio comparándolo con elementos en mid – 1 y mid + 1 .
- Si el elemento máximo no está en el medio (ni medio ni medio + 1), entonces el elemento máximo se encuentra en la mitad izquierda o en la mitad derecha.
- Si el elemento medio es mayor que el último elemento, entonces el elemento máximo se encuentra en la mitad izquierda.
- De lo contrario, el elemento máximo se encuentra en la mitad derecha.
A continuación se muestra la implementación del enfoque anterior:
C++
#include <bits/stdc++.h>
using namespace std;
// Function to return the maximum element
int findMax(int arr[], int low, int high)
{
if (high == low)
return arr[low];
// Find mid
int mid = low + (high - low) / 2;
// Check if mid reaches 0 ,it is greater than next element or not
if(mid==0 && arr[mid]>arr[mid+1])
{
return arr[mid];
}
// Check if mid itself is maximum element
if (mid < high && arr[mid + 1] < arr[mid] && mid>0 && arr[mid]>arr[mid-1]) {
return arr[mid];
}
// Decide whether we need to go to
// the left half or the right half
if (arr[low] > arr[mid]) {
return findMax(arr, low, mid - 1);
}
else {
return findMax(arr, mid + 1, high);
}
}
// Driver code
int main()
{
int arr[] = { 6,5,4,3,2,1};
int n = sizeof(arr) / sizeof(arr[0]);
cout << findMax(arr, 0, n - 1);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to return the maximum element
static int findMax(int arr[], int low, int high)
{
// If there is only one element left
if (high == low)
return arr[low];
// Find mid
int mid = low + (high - low) / 2;
// Check if mid reaches 0 ,it is greater than next element or not
if(mid==0 && arr[mid]>arr[mid+1])
{
return arr[mid];
}
// Decide whether we need to go to
// the left half or the right half
if (arr[low] > arr[mid])
{
return findMax(arr, low, mid - 1);
}
else
{
return findMax(arr, mid + 1, high);
}
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 6,5,4,3,2,1 };
int n = arr.length;
System.out.println(findMax(arr, 0, n - 1));
}
}
Python3
# Python3 implementation of the approach # Function to return the maximum element def findMax(arr, low, high): # If there is only one element left if (high == low): return arr[low] # Find mid mid = low + (high - low) // 2 # Check if mid reaches 0 ,it is greater than next element or not if(mid==0 and arr[mid]>arr[mid+1]): return arr[mid] # Check if mid itself is maximum element if (mid < high and arr[mid + 1] < arr[mid] and mid>0 and arr[mid]>arr[mid-1]): return arr[mid] # Decide whether we need to go to # the left half or the right half if (arr[low] > arr[mid]): return findMax(arr, low, mid - 1) else: return findMax(arr, mid + 1, high) # Driver code arr = [6,5,4,3,2,1] n = len(arr) print(findMax(arr, 0, n - 1))
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the maximum element
static int findMax(int []arr,
int low, int high)
{
// If there is only one element left
if (high == low)
return arr[low];
// Find mid
int mid = low + (high - low) / 2;
// Check if mid reaches 0 ,it is greater than next element or not
if(mid==0 && arr[mid]>arr[mid+1])
return arr[mid];
// Check if mid itself is maximum element
if (mid < high && arr[mid + 1] < arr[mid] && mid>0 && arr[mid]>arr[mid-1])
{
return arr[mid];
}
// Decide whether we need to go to
// the left half or the right half
if (arr[low] > arr[mid])
{
return findMax(arr, low, mid - 1);
}
else
{
return findMax(arr, mid + 1, high);
}
}
// Driver code
public static void Main()
{
int []arr = { 6,5, 1, 2, 3, 4 };
int n = arr.Length;
Console.WriteLine(findMax(arr, 0, n - 1));
}
}
PHP
<?php
// PHP implementation of the approach
// Function to return the maximum element
function findMax($arr, $low, $high)
{
// This condition is for the case when
// array is not rotated at all
if ($high <= $low)
return $arr[$low];
// Find mid
$mid = $low + ($high - $low) / 2;
// Check if mid reaches 0 ,it is greater than next element or not
if ($mid==0 && $arr[$mid]>$arr[$mid-1])
return $arr[0];
// Check if mid itself is maximum element
if ($mid < $high && $arr[$mid + 1] < $arr[$mid] && $mid > 0 && $arr[$mid]>$arr[$mid-1])
{
return $arr[$mid];
}
// Decide whether we need to go to
// the left half or the right half
if ($arr[$low] > $arr[$mid])
{
return findMax($arr, $low, $mid - 1);
}
else
{
return findMax($arr, $mid + 1, $high);
}
}
// Driver code
$arr = array(5,6,1,2,3,4);
$n = sizeof($arr);
echo findMax($arr, 0, $n - 1);
Javascript
<script>
// Java script implementation of the approach
// Function to return the maximum element
function findMax(arr,low,high)
{
// If there is only one element left
if (high == low)
return arr[low];
// Find mid
let mid = low + (high - low) / 2;
// Check if mid reaches 0 ,it is greater than next element or not
if(mid==0 && arr[mid]>arr[mid+1])
{
return arr[mid];
}
// Check if mid itself is maximum element
if (mid < high && arr[mid + 1] < arr[mid] && mid>0 && arr[mid]>arr[mid-1])
{
return arr[mid];
}
// Decide whether we need to go to
// the left half or the right half
if (arr[low] > arr[mid])
{
return findMax(arr, low, mid - 1);
}
else
{
return findMax(arr, mid + 1, high);
}
}
// Driver code
let arr = [ 5, 6, 1, 2, 3, 4 ];
let n = arr.length;
document.write(findMax(arr, 0, n-1 ));
</script>
Producción:
6
Complejidad de tiempo: O (logn), donde n representa el tamaño de la array dada.
Espacio auxiliar: O (logn) debido al espacio de pila recursivo.