Найдите локальные минимумы в массиве

Опубликовано: 26 Января, 2022

Для массива arr [0 .. n-1] различных целых чисел задача состоит в том, чтобы найти в нем локальные минимумы. Мы говорим, что элемент arr [x] является локальным минимумом, если он меньше или равен обоим его соседям.

  • Для угловых элементов нам нужно рассматривать только одного соседа для сравнения.
  • В массиве может быть несколько локальных минимумов, нам нужно найти любой из них.

Примеры:

Ввод: arr [] = {9, 6, 3, 14, 5, 7, 4};
Выход: Индекс локальных минимумов равен 2.
На выходе будет напечатан индекс 3, потому что это 
меньше, чем оба его соседа. 
Обратите внимание, что индексы элементов 5 и 4 равны 
также допустимые выходы.

Ввод: arr [] = {23, 8, 15, 2, 3};
Выход: индекс локальных минимумов равен 1.

Ввод: arr [] = {1, 2, 3};
Выход: Индекс локальных минимумов равен 0

Ввод: arr [] = {3, 2, 1};
Выход: Индекс локальных минимумов равен 2.

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Простое решение - выполнить линейное сканирование массива, и как только мы найдем локальный минимум, мы вернем его. В худшем случае временная сложность этого метода будет O (n).

Эффективное решение основано на двоичном поиске. Сравниваем средний элемент с его соседями. Если средний элемент не больше любого из своих соседей, мы возвращаем его. Если средний элемент больше, чем его левый сосед, то в левой половине всегда есть локальные минимумы (почему? Возьмите несколько примеров). Если средний элемент больше, чем его правый сосед, то всегда есть локальные минимумы в правой половине (по той же причине, что и левая половина).

Below is the implementation of the above idea :

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


Output:
Index of a local minima is 2

Сложность времени: O (Log n)


Связанная проблема:
Найдите пиковый элемент

Эта статья предоставлена Рошни Агарвалом . Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью на сайте deposit.geeksforgeeks.org или отправить свою статью по электронной почте: grant@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.

Вниманию читателя! Не переставай учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

РЕКОМЕНДУЕМЫЕ СТАТЬИ