Dada una array arr[0 .. n-1] de enteros distintos , la tarea es encontrar un mínimo local en ella. Decimos que un elemento arr[x] es un mínimo local si es menor que sus dos vecinos.
- Para los elementos de esquina, debemos considerar solo un vecino para la comparación.
- Puede haber más de un mínimo local en una array, necesitamos encontrar uno de ellos.
Ejemplos:
Input: arr[] = {9, 6, 3, 14, 5, 7, 4};
Output: Index of local minima is 2
The output prints index of 3 because it is
smaller than both of its neighbors.
Note that indexes of elements 5 and 4 are
also valid outputs.
Input: arr[] = {23, 8, 15, 2, 3};
Output: Index of local minima is 1
Input: arr[] = {1, 2, 3};
Output: Index of local minima is 0
Input: arr[] = {3, 2, 1};
Output: Index of local minima is 2
Una solución simple es hacer un escaneo lineal de la array y tan pronto como encontremos un mínimo local, lo devolvemos. La complejidad temporal del peor de los casos de este método sería O(n).
Una solución eficiente se basa en la búsqueda binaria . Comparamos el elemento medio con sus vecinos. Si el elemento medio no es mayor que ninguno de sus vecinos, lo devolvemos. Si el elemento del medio es mayor que su vecino izquierdo, entonces siempre hay un mínimo local en la mitad izquierda (¿Por qué? Tome algunos ejemplos). Si el elemento del medio es mayor que su vecino derecho, entonces siempre hay un mínimo local en la mitad derecha (por la misma razón que la mitad izquierda).
A continuación se muestra la implementación de la idea anterior:
C++
// A C++ program to find a local minima in an array
#include <stdio.h>
// A binary search based function that returns
// index of a local minima.
int localMinUtil(int arr[], int low, int high, int n)
{
// Find index of middle element
int mid = low + (high - low)/2; /* (low + high)/2 */
// Compare middle element with its neighbours
// (if neighbours exist)
if ((mid == 0 || arr[mid-1] > arr[mid]) &&
(mid == n-1 || arr[mid+1] > arr[mid]))
return mid;
// If middle element is not minima and its left
// neighbour is smaller than it, then left half
// must have a local minima.
else if (mid > 0 && arr[mid-1] < arr[mid])
return localMinUtil(arr, low, (mid -1), n);
// If middle element is not minima and its right
// neighbour is smaller than it, then right half
// must have a local minima.
return localMinUtil(arr, (mid + 1), high, n);
}
// A wrapper over recursive function localMinUtil()
int localMin(int arr[], int n)
{
return localMinUtil(arr, 0, n-1, n);
}
/* Driver program to check above functions */
int main()
{
int arr[] = {4, 3, 1, 14, 16, 40};
int n = sizeof(arr)/sizeof(arr[0]);
printf("Index of a local minima is %d",
localMin(arr, n));
return 0;
}
Java
// A Java program to find a local minima in an array
import java.io.*;
class GFG
{
// A binary search based function that returns
// index of a local minima.
public static int localMinUtil(int[] arr, int low,
int high, int n)
{
// Find index of middle element
int mid = low + (high - low) / 2;
// Compare middle element with its neighbours
// (if neighbours exist)
if(mid == 0 || arr[mid - 1] > arr[mid] && mid == n - 1 ||
arr[mid] < arr[mid + 1])
return mid;
// If middle element is not minima and its left
// neighbour is smaller than it, then left half
// must have a local minima.
else if(mid > 0 && arr[mid - 1] < arr[mid])
return localMinUtil(arr, low, mid - 1, n);
// If middle element is not minima and its right
// neighbour is smaller than it, then right half
// must have a local minima.
return localMinUtil(arr, mid + 1, high, n);
}
// A wrapper over recursive function localMinUtil()
public static int localMin(int[] arr, int n)
{
return localMinUtil(arr, 0, n - 1, n);
}
public static void main (String[] args)
{
int arr[] = {4, 3, 1, 14, 16, 40};
int n = arr.length;
System.out.println("Index of a local minima is " + localMin(arr, n));
}
}
//This code is contributed by Dheerendra Singh
Python3
# Python3 program to find a
# local minima in an array
# A binary search based function that
# returns index of a local minima.
def localMinUtil(arr, low, high, n):
# Find index of middle element
mid = low + (high - low) // 2
# Compare middle element with its
# neighbours (if neighbours exist)
if(mid == 0 or arr[mid - 1] > arr[mid] and
mid == n - 1 or arr[mid] < arr[mid + 1]):
return mid
# If middle element is not minima and its left
# neighbour is smaller than it, then left half
# must have a local minima.
elif(mid > 0 and arr[mid - 1] < arr[mid]):
return localMinUtil(arr, low, mid - 1, n)
# If middle element is not minima and its right
# neighbour is smaller than it, then right half
# must have a local minima.
return localMinUtil(arr, mid + 1, high, n)
# A wrapper over recursive function localMinUtil()
def localMin(arr, n):
return localMinUtil(arr, 0, n - 1, n)
# Driver code
arr = [4, 3, 1, 14, 16, 40]
n = len(arr)
print("Index of a local minima is " ,
localMin(arr, n))
# This code is contributed by Anant Agarwal.
C#
// A C# program to find a
// local minima in an array
using System;
class GFG
{
// A binary search based function that returns
// index of a local minima.
public static int localMinUtil(int[] arr, int low,
int high, int n)
{
// Find index of middle element
int mid = low + (high - low) / 2;
// Compare middle element with its neighbours
// (if neighbours exist)
if(mid == 0 || arr[mid - 1] > arr[mid] &&
mid == n - 1 || arr[mid] < arr[mid + 1])
return mid;
// If middle element is not minima and its left
// neighbour is smaller than it, then left half
// must have a local minima.
else if(mid > 0 && arr[mid - 1] < arr[mid])
return localMinUtil(arr, low, mid - 1, n);
// If middle element is not minima and its right
// neighbour is smaller than it, then right half
// must have a local minima.
return localMinUtil(arr, mid + 1, high, n);
}
// A wrapper over recursive function localMinUtil()
public static int localMin(int[] arr, int n)
{
return localMinUtil(arr, 0, n - 1, n);
}
// Driver Code
public static void Main ()
{
int []arr = {4, 3, 1, 14, 16, 40};
int n = arr.Length;
Console.WriteLine("Index of a local minima is " +
localMin(arr, n));
}
}
// This code is contributed by vt_m.
PHP
<?php
// A PHP program to find a
// local minima in an array
// A binary search based
// function that returns
// index of a local minima.
function localMinUtil($arr, $low, $high, $n)
{
// Find index of middle element
/* (low + high)/2 */
$mid = $low + ($high - $low) / 2;
// Compare middle element
// with its neighbours
// (if neighbours exist)
if (($mid == 0 or $arr[$mid - 1] > $arr[$mid]) and
($mid == $n - 1 or $arr[$mid + 1] > $arr[$mid]))
return $mid;
// If middle element is not
// minima and its left
// neighbour is smaller than
// it, then left half
// must have a local minima.
else if ($mid > 0 and $arr[$mid - 1] < $arr[$mid])
return localMinUtil($arr, $low, ($mid - 1), $n);
// If middle element is not
// minima and its right
// neighbour is smaller than
// it, then right half
// must have a local minima.
return localMinUtil(arr, (mid + 1), high, n);
}
// A wrapper over recursive
// function localMinUtil()
function localMin( $arr, $n)
{
return floor(localMinUtil($arr, 0, $n - 1, $n));
}
// Driver Code
$arr = array(4, 3, 1, 14, 16, 40);
$n = count($arr);
echo "Index of a local minima is ",
localMin($arr, $n);
// This code is contributed by anuj_67.
?>
Producción:
Index of a local minima is 2
Complejidad de tiempo: O(Log n)
Problema relacionado:
encontrar un elemento de pico
Este artículo es una contribución de Roshni Agarwal . 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.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA