Máximo y mínimo de una array usando el número mínimo de comparaciones

Escriba una función C para devolver el mínimo y el máximo en una array. Su programa debe hacer el mínimo número de comparaciones. 

En primer lugar, ¿cómo devolvemos múltiples valores de una función C? Podemos hacerlo usando estructuras o punteros. 
Hemos creado una estructura llamada par (que contiene mínimo y máximo) para devolver múltiples valores. 

C++

struct pair {
    int min;
    int max;
};
 
// This code contributed by Aarti_Rathi

C

struct pair
{
  int min;
  int max;
}; 

Java

static class pair
{
  int min;
  int max;
};
 
// This code contributed by Rajput-Ji

Python3

# Python3 implementation
 
class pair:
     
    def __init__(self):
        self.min = None
        self.max = None
 
 
# This code contributed by phasing17

C#

public static class pair {
    public int min;
    public int max;
};
// This code contributed by Rajput-Ji

Javascript

<script>
 
class pair
{
  constructor(){
    this.min = null;
    this.max = null;
  }
};
 
// This code contributed by Saurabh Jaiswal
 
</script>

Y la declaración de la función se convierte en: struct pair getMinMax(int ​​arr[], int n) donde arr[] es la array de tamaño n cuyo mínimo y máximo son necesarios. 

 

Complete Interview Preparation - GFG

MÉTODO 1 (Búsqueda lineal simple) 
Inicialice los valores de min y max como mínimo y máximo de los dos primeros elementos respectivamente. A partir del 3, compare cada elemento con max y min, y cambie max y min en consecuencia (es decir, si el elemento es más pequeño que min, cambie min, de lo contrario, si el elemento es mayor que max, cambie max, de lo contrario ignore el elemento) 

C++

// C++ program of above implementation
#include<iostream>
using namespace std;
 
// Pair struct is used to return
// two values from getMinMax()
struct Pair
{
    int min;
    int max;
};
 
Pair getMinMax(int arr[], int n)
{
    struct Pair minmax;    
    int i;
     
    // If there is only one element
    // then return it as min and max both
    if (n == 1)
    {
        minmax.max = arr[0];
        minmax.min = arr[0];    
        return minmax;
    }
     
    // If there are more than one elements,
    // then initialize min and max
    if (arr[0] > arr[1])
    {
        minmax.max = arr[0];
        minmax.min = arr[1];
    }
    else
    {
        minmax.max = arr[1];
        minmax.min = arr[0];
    }
     
    for(i = 2; i < n; i++)
    {
        if (arr[i] > minmax.max)    
            minmax.max = arr[i];
             
        else if (arr[i] < minmax.min)    
            minmax.min = arr[i];
    }
    return minmax;
}
 
// Driver code
int main()
{
    int arr[] = { 1000, 11, 445,
                  1, 330, 3000 };
    int arr_size = 6;
     
    struct Pair minmax = getMinMax(arr, arr_size);
     
    cout << "Minimum element is "
         << minmax.min << endl;
    cout << "Maximum element is "
         << minmax.max;
          
    return 0;
}
 
// This code is contributed by nik_3112

C

/* structure is used to return two values from minMax() */
#include<stdio.h>
struct pair
{
  int min;
  int max;
}; 
 
struct pair getMinMax(int arr[], int n)
{
  struct pair minmax;    
  int i;
   
  /*If there is only one element then return it as min and max both*/
  if (n == 1)
  {
     minmax.max = arr[0];
     minmax.min = arr[0];    
     return minmax;
  }   
 
  /* If there are more than one elements, then initialize min
      and max*/
  if (arr[0] > arr[1]) 
  {
      minmax.max = arr[0];
      minmax.min = arr[1];
  } 
  else
  {
      minmax.max = arr[1];
      minmax.min = arr[0];
  }   
 
  for (i = 2; i<n; i++)
  {
    if (arr[i] >  minmax.max)     
      minmax.max = arr[i];
   
    else if (arr[i] <  minmax.min)     
      minmax.min = arr[i];
  }
   
  return minmax;
}
 
/* Driver program to test above function */
int main()
{
  int arr[] = {1000, 11, 445, 1, 330, 3000};
  int arr_size = 6;
  struct pair minmax = getMinMax (arr, arr_size);
  printf("nMinimum element is %d", minmax.min);
  printf("nMaximum element is %d", minmax.max);
  getchar();
} 

Java

// Java program of above implementation
public class GFG {
/* Class Pair is used to return two values from getMinMax() */
    static class Pair {
 
        int min;
        int max;
    }
 
    static Pair getMinMax(int arr[], int n) {
        Pair minmax = new  Pair();
        int i;
 
        /*If there is only one element then return it as min and max both*/
        if (n == 1) {
            minmax.max = arr[0];
            minmax.min = arr[0];
            return minmax;
        }
 
        /* If there are more than one elements, then initialize min
    and max*/
        if (arr[0] > arr[1]) {
            minmax.max = arr[0];
            minmax.min = arr[1];
        } else {
            minmax.max = arr[1];
            minmax.min = arr[0];
        }
 
        for (i = 2; i < n; i++) {
            if (arr[i] > minmax.max) {
                minmax.max = arr[i];
            } else if (arr[i] < minmax.min) {
                minmax.min = arr[i];
            }
        }
 
        return minmax;
    }
 
    /* Driver program to test above function */
    public static void main(String args[]) {
        int arr[] = {1000, 11, 445, 1, 330, 3000};
        int arr_size = 6;
        Pair minmax = getMinMax(arr, arr_size);
        System.out.printf("\nMinimum element is %d", minmax.min);
        System.out.printf("\nMaximum element is %d", minmax.max);
 
    }
 
}

Python3

# Python program of above implementation
 
# structure is used to return two values from minMax()
 
class pair:
    def __init__(self):
        self.min = 0
        self.max = 0
 
def getMinMax(arr: list, n: int) -> pair:
    minmax = pair()
 
    # If there is only one element then return it as min and max both
    if n == 1:
        minmax.max = arr[0]
        minmax.min = arr[0]
        return minmax
 
    # If there are more than one elements, then initialize min
    # and max
    if arr[0] > arr[1]:
        minmax.max = arr[0]
        minmax.min = arr[1]
    else:
        minmax.max = arr[1]
        minmax.min = arr[0]
 
    for i in range(2, n):
        if arr[i] > minmax.max:
            minmax.max = arr[i]
        elif arr[i] < minmax.min:
            minmax.min = arr[i]
 
    return minmax
 
# Driver Code
if __name__ == "__main__":
    arr = [1000, 11, 445, 1, 330, 3000]
    arr_size = 6
    minmax = getMinMax(arr, arr_size)
    print("Minimum element is", minmax.min)
    print("Maximum element is", minmax.max)
 
# This code is contributed by
# sanjeev2552

C#

// C# program of above implementation
using System;
 
class GFG
{
    /* Class Pair is used to return
    two values from getMinMax() */
    class Pair
    {
        public int min;
        public int max;
    }
 
    static Pair getMinMax(int []arr, int n)
    {
        Pair minmax = new Pair();
        int i;
 
        /* If there is only one element
        then return it as min and max both*/
        if (n == 1)
        {
            minmax.max = arr[0];
            minmax.min = arr[0];
            return minmax;
        }
 
        /* If there are more than one elements,
        then initialize min and max*/
        if (arr[0] > arr[1])
        {
            minmax.max = arr[0];
            minmax.min = arr[1];
        }
        else
        {
            minmax.max = arr[1];
            minmax.min = arr[0];
        }
 
        for (i = 2; i < n; i++)
        {
            if (arr[i] > minmax.max)
            {
                minmax.max = arr[i];
            }
            else if (arr[i] < minmax.min)
            {
                minmax.min = arr[i];
            }
        }
        return minmax;
    }
 
    // Driver Code
    public static void Main(String []args)
    {
        int []arr = {1000, 11, 445, 1, 330, 3000};
        int arr_size = 6;
        Pair minmax = getMinMax(arr, arr_size);
        Console.Write("Minimum element is {0}",
                                   minmax.min);
        Console.Write("\nMaximum element is {0}",
                                     minmax.max);
    }
}
 
// This code is contributed by PrinciRaj1992

Javascript

<script>
// JavaScript program of above implementation
 
/* Class Pair is used to return two values from getMinMax() */
    function getMinMax(arr, n)
    {
        minmax = new  Array();
        var i;
        var min;
        var max;
 
        /*If there is only one element then return it as min and max both*/
        if (n == 1) {
            minmax.max = arr[0];
            minmax.min = arr[0];
            return minmax;
        }
 
        /* If there are more than one elements, then initialize min
    and max*/
        if (arr[0] > arr[1]) {
            minmax.max = arr[0];
            minmax.min = arr[1];
        } else {
            minmax.max = arr[1];
            minmax.min = arr[0];
        }
 
        for (i = 2; i < n; i++) {
            if (arr[i] > minmax.max) {
                minmax.max = arr[i];
            } else if (arr[i] < minmax.min) {
                minmax.min = arr[i];
            }
        }
 
        return minmax;
    }
 
    /* Driver program to test above function */
     
        var arr = [1000, 11, 445, 1, 330, 3000];
        var arr_size = 6;
        minmax = getMinMax(arr, arr_size);
        document.write("\nMinimum element is " ,minmax.min +"<br>");
        document.write("\nMaximum element is " , minmax.max);
 
// This code is contributed by shivanisinghss2110
</script>

Producción: 

Minimum element is 1
Maximum element is 3000

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(1) ya que no se necesitaba espacio extra.

En este método, el número total de comparaciones es 1 + 2(n-2) en el peor de los casos y 1 + n – 2 en el mejor de los casos. 
En la implementación anterior, el peor caso ocurre cuando los elementos se ordenan en orden descendente y el mejor caso ocurre cuando los elementos se ordenan en orden ascendente.

MÉTODO 2 (Método de torneo) 
Divida la array en dos partes y compare los máximos y mínimos de las dos partes para obtener el máximo y el mínimo de toda la array.

Pair MaxMin(array, array_size)
   if array_size = 1
      return element as both max and min
   else if arry_size = 2
      one comparison to determine max and min
      return that pair
   else    /* array_size  > 2 */
      recur for max and min of left half
      recur for max and min of right half
      one comparison determines true max of the two candidates
      one comparison determines true min of the two candidates
      return the pair of max and min

Implementación 

C++

// C++ program of above implementation
#include<iostream>
using namespace std;
 
// structure is used to return
// two values from minMax()
struct Pair
{
    int min;
    int max;
};
 
struct Pair getMinMax(int arr[], int low,
                                 int high)
{
    struct Pair minmax, mml, mmr;    
    int mid;
     
    // If there is only one element
    if (low == high)
    {
        minmax.max = arr[low];
        minmax.min = arr[low];    
        return minmax;
    }
     
    // If there are two elements
    if (high == low + 1)
    {
        if (arr[low] > arr[high])
        {
            minmax.max = arr[low];
            minmax.min = arr[high];
        }
        else
        {
            minmax.max = arr[high];
            minmax.min = arr[low];
        }
        return minmax;
    }
     
    // If there are more than 2 elements
    mid = (low + high) / 2;
    mml = getMinMax(arr, low, mid);
    mmr = getMinMax(arr, mid + 1, high);
     
    // Compare minimums of two parts
    if (mml.min < mmr.min)
        minmax.min = mml.min;
    else
        minmax.min = mmr.min;    
     
    // Compare maximums of two parts
    if (mml.max > mmr.max)
        minmax.max = mml.max;
    else
        minmax.max = mmr.max;    
     
    return minmax;
}
 
// Driver code
int main()
{
    int arr[] = { 1000, 11, 445,
                  1, 330, 3000 };
    int arr_size = 6;
     
    struct Pair minmax = getMinMax(arr, 0,
                             arr_size - 1);
                              
    cout << "Minimum element is "
         << minmax.min << endl;
    cout << "Maximum element is "
         << minmax.max;
          
    return 0;
}
 
// This code is contributed by nik_3112

C

/* structure is used to return two values from minMax() */
#include<stdio.h>
struct pair
{
  int min;
  int max;
}; 
 
struct pair getMinMax(int arr[], int low, int high)
{
  struct pair minmax, mml, mmr;      
  int mid;
   
  // If there is only one element
  if (low == high)
  {
     minmax.max = arr[low];
     minmax.min = arr[low];    
     return minmax;
  }   
   
  /* If there are two elements */
  if (high == low + 1)
  { 
     if (arr[low] > arr[high]) 
     {
        minmax.max = arr[low];
        minmax.min = arr[high];
     } 
     else
     {
        minmax.max = arr[high];
        minmax.min = arr[low];
     } 
     return minmax;
  }
   
  /* If there are more than 2 elements */
  mid = (low + high)/2; 
  mml = getMinMax(arr, low, mid);
  mmr = getMinMax(arr, mid+1, high); 
   
  /* compare minimums of two parts*/
  if (mml.min < mmr.min)
    minmax.min = mml.min;
  else
    minmax.min = mmr.min;    
 
  /* compare maximums of two parts*/
  if (mml.max > mmr.max)
    minmax.max = mml.max;
  else
    minmax.max = mmr.max;    
  
  return minmax;
}
 
/* Driver program to test above function */
int main()
{
  int arr[] = {1000, 11, 445, 1, 330, 3000};
  int arr_size = 6;
  struct pair minmax = getMinMax(arr, 0, arr_size-1);
  printf("nMinimum element is %d", minmax.min);
  printf("nMaximum element is %d", minmax.max);
  getchar();
}

Java

// Java program of above implementation
public class GFG {
/* Class Pair is used to return two values from getMinMax() */
    static class Pair {
 
        int min;
        int max;
    }
 
    static Pair getMinMax(int arr[], int low, int high) {
        Pair minmax = new Pair();
        Pair mml = new Pair();
        Pair mmr = new Pair();
        int mid;
 
        // If there is only one element
        if (low == high) {
            minmax.max = arr[low];
            minmax.min = arr[low];
            return minmax;
        }
 
        /* If there are two elements */
        if (high == low + 1) {
            if (arr[low] > arr[high]) {
                minmax.max = arr[low];
                minmax.min = arr[high];
            } else {
                minmax.max = arr[high];
                minmax.min = arr[low];
            }
            return minmax;
        }
 
        /* If there are more than 2 elements */
        mid = (low + high) / 2;
        mml = getMinMax(arr, low, mid);
        mmr = getMinMax(arr, mid + 1, high);
 
        /* compare minimums of two parts*/
        if (mml.min < mmr.min) {
            minmax.min = mml.min;
        } else {
            minmax.min = mmr.min;
        }
 
        /* compare maximums of two parts*/
        if (mml.max > mmr.max) {
            minmax.max = mml.max;
        } else {
            minmax.max = mmr.max;
        }
 
        return minmax;
    }
 
    /* Driver program to test above function */
    public static void main(String args[]) {
        int arr[] = {1000, 11, 445, 1, 330, 3000};
        int arr_size = 6;
        Pair minmax = getMinMax(arr, 0, arr_size - 1);
        System.out.printf("\nMinimum element is %d", minmax.min);
        System.out.printf("\nMaximum element is %d", minmax.max);
 
    }
}

Python3

# Python program of above implementation
def getMinMax(low, high, arr):
    arr_max = arr[low]
    arr_min = arr[low]
     
    # If there is only one element
    if low == high:
        arr_max = arr[low]
        arr_min = arr[low]
        return (arr_max, arr_min)
         
    # If there is only two element
    elif high == low + 1:
        if arr[low] > arr[high]:
            arr_max = arr[low]
            arr_min = arr[high]
        else:
            arr_max = arr[high]
            arr_min = arr[low]
        return (arr_max, arr_min)
    else:
         
        # If there are more than 2 elements
        mid = int((low + high) / 2)
        arr_max1, arr_min1 = getMinMax(low, mid, arr)
        arr_max2, arr_min2 = getMinMax(mid + 1, high, arr)
 
    return (max(arr_max1, arr_max2), min(arr_min1, arr_min2))
 
# Driver code
arr = [1000, 11, 445, 1, 330, 3000]
high = len(arr) - 1
low = 0
arr_max, arr_min = getMinMax(low, high, arr)
print('Minimum element is ', arr_min)
print('nMaximum element is ', arr_max)
 
# This code is contributed by DeepakChhitarka

C#

// C# implementation of the approach
using System;
                     
public class GFG {
/* Class Pair is used to return two values from getMinMax() */
    public class Pair {
  
        public int min;
        public int max;
    }
  
    static Pair getMinMax(int []arr, int low, int high) {
        Pair minmax = new Pair();
        Pair mml = new Pair();
        Pair mmr = new Pair();
        int mid;
  
        // If there is only one element
        if (low == high) {
            minmax.max = arr[low];
            minmax.min = arr[low];
            return minmax;
        }
  
        /* If there are two elements */
        if (high == low + 1) {
            if (arr[low] > arr[high]) {
                minmax.max = arr[low];
                minmax.min = arr[high];
            } else {
                minmax.max = arr[high];
                minmax.min = arr[low];
            }
            return minmax;
        }
  
        /* If there are more than 2 elements */
        mid = (low + high) / 2;
        mml = getMinMax(arr, low, mid);
        mmr = getMinMax(arr, mid + 1, high);
  
        /* compare minimums of two parts*/
        if (mml.min < mmr.min) {
            minmax.min = mml.min;
        } else {
            minmax.min = mmr.min;
        }
  
        /* compare maximums of two parts*/
        if (mml.max > mmr.max) {
            minmax.max = mml.max;
        } else {
            minmax.max = mmr.max;
        }
  
        return minmax;
    }
  
    /* Driver program to test above function */
    public static void Main(String []args) {
        int []arr = {1000, 11, 445, 1, 330, 3000};
        int arr_size = 6;
        Pair minmax = getMinMax(arr, 0, arr_size - 1);
        Console.Write("\nMinimum element is {0}", minmax.min);
        Console.Write("\nMaximum element is {0}", minmax.max);
  
    }
}
 
// This code contributed by Rajput-Ji

Javascript

<script>
// Javascript program of above implementation
  
    /* Class Pair is used to return two values from getMinMax() */
     class Pair {
         constructor(){
        this.min = -1;
        this.max = 10000000;
         }
    }
 
     function getMinMax(arr , low , high) {
        var minmax = new Pair();
        var mml = new Pair();
        var mmr = new Pair();
        var mid;
 
        // If there is only one element
        if (low == high) {
            minmax.max = arr[low];
            minmax.min = arr[low];
            return minmax;
        }
 
        /* If there are two elements */
        if (high == low + 1) {
            if (arr[low] > arr[high]) {
                minmax.max = arr[low];
                minmax.min = arr[high];
            } else {
                minmax.max = arr[high];
                minmax.min = arr[low];
            }
            return minmax;
        }
 
        /* If there are more than 2 elements */
        mid = parseInt((low + high) / 2);
        mml = getMinMax(arr, low, mid);
        mmr = getMinMax(arr, mid + 1, high);
 
        /* compare minimums of two parts */
        if (mml.min < mmr.min) {
            minmax.min = mml.min;
        } else {
            minmax.min = mmr.min;
        }
 
        /* compare maximums of two parts */
        if (mml.max > mmr.max) {
            minmax.max = mml.max;
        } else {
            minmax.max = mmr.max;
        }
 
        return minmax;
    }
 
    /* Driver program to test above function */
        var arr = [ 1000, 11, 445, 1, 330, 3000 ];
        var arr_size = 6;
        var minmax = getMinMax(arr, 0, arr_size - 1);
        document.write("\nMinimum element is ", minmax.min);
        document.write("<br/>Maximum element is ", minmax.max);
 
// This code is contributed by Rajput-Ji
</script>

Producción: 

Minimum element is 1
Maximum element is 3000

Complejidad de tiempo: O(n)

Espacio auxiliar: O (log n) ya que el espacio de la pila se llenará para la altura máxima del árbol formado durante las llamadas recursivas, igual que un árbol binario.

Número total de comparaciones: sea el número de comparaciones T(n). T(n) se puede escribir de la siguiente manera: 
Paradigma algorítmico: divide y vencerás 

             
  T(n) = T(floor(n/2)) + T(ceil(n/2)) + 2  
  T(2) = 1
  T(1) = 0

Si n es una potencia de 2, entonces podemos escribir T(n) como: 

   T(n) = 2T(n/2) + 2

Después de resolver la recursividad anterior, obtenemos 

  T(n)  = 3n/2 -2

Por lo tanto, el enfoque hace 3n/2 -2 comparaciones si n es una potencia de 2. Y hace más de 3n/2 -2 comparaciones si n no es una potencia de 2.

MÉTODO 3 (Comparar en pares) 
Si n es impar, entonces inicialice min y max como primer elemento. 
Si n es par, inicialice min y max como mínimo y máximo de los dos primeros elementos respectivamente. 
Para el resto de los elementos, selecciónelos en pares y compare su 
máximo y mínimo con máximo y mínimo respectivamente. 

C++

// C++ program of above implementation
#include<iostream>
using namespace std;
 
// Structure is used to return
// two values from minMax()
struct Pair
{
    int min;
    int max;
};
 
struct Pair getMinMax(int arr[], int n)
{
    struct Pair minmax;    
    int i;
     
    // If array has even number of elements
    // then initialize the first two elements
    // as minimum and maximum
    if (n % 2 == 0)
    {
        if (arr[0] > arr[1])    
        {
            minmax.max = arr[0];
            minmax.min = arr[1];
        }
        else
        {
            minmax.min = arr[0];
            minmax.max = arr[1];
        }
         
        // Set the starting index for loop
        i = 2;
    }
     
    // If array has odd number of elements
    // then initialize the first element as
    // minimum and maximum
    else
    {
        minmax.min = arr[0];
        minmax.max = arr[0];
         
        // Set the starting index for loop
        i = 1;
    }
     
    // In the while loop, pick elements in
    // pair and compare the pair with max
    // and min so far
    while (i < n - 1)
    {        
        if (arr[i] > arr[i + 1])        
        {
            if(arr[i] > minmax.max)    
                minmax.max = arr[i];
                 
            if(arr[i + 1] < minmax.min)        
                minmax.min = arr[i + 1];    
        }
        else       
        {
            if (arr[i + 1] > minmax.max)    
                minmax.max = arr[i + 1];
                 
            if (arr[i] < minmax.min)        
                minmax.min = arr[i];    
        }
         
        // Increment the index by 2 as
        // two elements are processed in loop
        i += 2;
    }        
    return minmax;
}
 
// Driver code
int main()
{
    int arr[] = { 1000, 11, 445,
                1, 330, 3000 };
    int arr_size = 6;
     
    Pair minmax = getMinMax(arr, arr_size);
     
    cout << "nMinimum element is "
        << minmax.min << endl;
    cout << "nMaximum element is "
        << minmax.max;
         
    return 0;
}
 
// This code is contributed by nik_3112

C

#include<stdio.h>
 
/* structure is used to return two values from minMax() */
struct pair
{
  int min;
  int max;
}; 
 
struct pair getMinMax(int arr[], int n)
{
  struct pair minmax;    
  int i; 
 
  /* If array has even number of elements then
    initialize the first two elements as minimum and
    maximum */
  if (n%2 == 0)
  {        
    if (arr[0] > arr[1])    
    {
      minmax.max = arr[0];
      minmax.min = arr[1];
    } 
    else
    {
      minmax.min = arr[0];
      minmax.max = arr[1];
    }
    i = 2;  /* set the starting index for loop */
  } 
 
   /* If array has odd number of elements then
    initialize the first element as minimum and
    maximum */
  else
  {
    minmax.min = arr[0];
    minmax.max = arr[0];
    i = 1;  /* set the starting index for loop */
  }
   
  /* In the while loop, pick elements in pair and
     compare the pair with max and min so far */   
  while (i < n-1) 
  {         
    if (arr[i] > arr[i+1])         
    {
      if(arr[i] > minmax.max)       
        minmax.max = arr[i];
      if(arr[i+1] < minmax.min)         
        minmax.min = arr[i+1];       
    }
    else        
    {
      if (arr[i+1] > minmax.max)       
        minmax.max = arr[i+1];
      if (arr[i] < minmax.min)         
        minmax.min = arr[i];       
    }       
    i += 2; /* Increment the index by 2 as two
               elements are processed in loop */
  }           
 
  return minmax;
}   
 
/* Driver program to test above function */
int main()
{
  int arr[] = {1000, 11, 445, 1, 330, 3000};
  int arr_size = 6;
  struct pair minmax = getMinMax (arr, arr_size);
  printf("nMinimum element is %d", minmax.min);
  printf("nMaximum element is %d", minmax.max);
  getchar();
}

Java

// Java program of above implementation
public class GFG {
 
/* Class Pair is used to return two values from getMinMax() */
    static class Pair {
 
        int min;
        int max;
    }
 
    static Pair getMinMax(int arr[], int n) {
        Pair minmax = new Pair();
        int i;
        /* If array has even number of elements then 
    initialize the first two elements as minimum and 
    maximum */
        if (n % 2 == 0) {
            if (arr[0] > arr[1]) {
                minmax.max = arr[0];
                minmax.min = arr[1];
            } else {
                minmax.min = arr[0];
                minmax.max = arr[1];
            }
            i = 2;
            /* set the starting index for loop */
        } /* If array has odd number of elements then 
    initialize the first element as minimum and 
    maximum */ else {
            minmax.min = arr[0];
            minmax.max = arr[0];
            i = 1;
            /* set the starting index for loop */
        }
 
        /* In the while loop, pick elements in pair and 
     compare the pair with max and min so far */
        while (i < n - 1) {
            if (arr[i] > arr[i + 1]) {
                if (arr[i] > minmax.max) {
                    minmax.max = arr[i];
                }
                if (arr[i + 1] < minmax.min) {
                    minmax.min = arr[i + 1];
                }
            } else {
                if (arr[i + 1] > minmax.max) {
                    minmax.max = arr[i + 1];
                }
                if (arr[i] < minmax.min) {
                    minmax.min = arr[i];
                }
            }
            i += 2;
            /* Increment the index by 2 as two 
               elements are processed in loop */
        }
 
        return minmax;
    }
 
    /* Driver program to test above function */
    public static void main(String args[]) {
        int arr[] = {1000, 11, 445, 1, 330, 3000};
        int arr_size = 6;
        Pair minmax = getMinMax(arr, arr_size);
        System.out.printf("\nMinimum element is %d", minmax.min);
        System.out.printf("\nMaximum element is %d", minmax.max);
 
    }
}

Python3

# Python3 program of above implementation
def getMinMax(arr):
     
    n = len(arr)
     
    # If array has even number of elements then
    # initialize the first two elements as minimum
    # and maximum
    if(n % 2 == 0):
        mx = max(arr[0], arr[1])
        mn = min(arr[0], arr[1])
         
        # set the starting index for loop
        i = 2
         
    # If array has odd number of elements then
    # initialize the first element as minimum
    # and maximum
    else:
        mx = mn = arr[0]
         
        # set the starting index for loop
        i = 1
         
    # In the while loop, pick elements in pair and
    # compare the pair with max and min so far
    while(i < n - 1):
        if arr[i] < arr[i + 1]:
            mx = max(mx, arr[i + 1])
            mn = min(mn, arr[i])
        else:
            mx = max(mx, arr[i])
            mn = min(mn, arr[i + 1])
             
        # Increment the index by 2 as two
        # elements are processed in loop
        i += 2
     
    return (mx, mn)
     
# Driver Code
if __name__ =='__main__':
     
    arr = [1000, 11, 445, 1, 330, 3000]
    mx, mn = getMinMax(arr)
    print("Minimum element is", mn)
    print("Maximum element is", mx)
     
# This code is contributed by Kaustav

C#

// C# program of above implementation
using System;
     
class GFG
{
 
    /* Class Pair is used to return
       two values from getMinMax() */
    public class Pair
    {
        public int min;
        public int max;
    }
 
    static Pair getMinMax(int []arr, int n)
    {
        Pair minmax = new Pair();
        int i;
         
        /* If array has even number of elements
        then initialize the first two elements
        as minimum and maximum */
        if (n % 2 == 0)
        {
            if (arr[0] > arr[1])
            {
                minmax.max = arr[0];
                minmax.min = arr[1];
            }
            else
            {
                minmax.min = arr[0];
                minmax.max = arr[1];
            }
            i = 2;
        }
         
        /* set the starting index for loop */
        /* If array has odd number of elements then
        initialize the first element as minimum and
        maximum */
        else
        {
            minmax.min = arr[0];
            minmax.max = arr[0];
            i = 1;
            /* set the starting index for loop */
        }
 
        /* In the while loop, pick elements in pair and
        compare the pair with max and min so far */
        while (i < n - 1)
        {
            if (arr[i] > arr[i + 1])
            {
                if (arr[i] > minmax.max)
                {
                    minmax.max = arr[i];
                }
                if (arr[i + 1] < minmax.min)
                {
                    minmax.min = arr[i + 1];
                }
            }
            else
            {
                if (arr[i + 1] > minmax.max)
                {
                    minmax.max = arr[i + 1];
                }
                if (arr[i] < minmax.min)
                {
                    minmax.min = arr[i];
                }
            }
            i += 2;
             
            /* Increment the index by 2 as two
            elements are processed in loop */
        }
        return minmax;
    }
 
    // Driver Code
    public static void Main(String []args)
    {
        int []arr = {1000, 11, 445, 1, 330, 3000};
        int arr_size = 6;
        Pair minmax = getMinMax(arr, arr_size);
        Console.Write("Minimum element is {0}",
                                   minmax.min);
        Console.Write("\nMaximum element is {0}",
                                     minmax.max);
    }
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// JavaScript program of above implementation
function getMinMax(arr){
     
    let n = arr.length
    let mx,mn,i
     
    // If array has even number of elements then
    // initialize the first two elements as minimum
    // and maximum
    if(n % 2 == 0){
        mx = Math.max(arr[0], arr[1])
        mn = Math.min(arr[0], arr[1])
         
        // set the starting index for loop
        i = 2
    }
         
    // If array has odd number of elements then
    // initialize the first element as minimum
    // and maximum
    else{
        mx = mn = arr[0]
         
        // set the starting index for loop
        i = 1
    }
         
    // In the while loop, pick elements in pair and
    // compare the pair with max and min so far
    while(i < n - 1){
        if(arr[i] < arr[i + 1]){
            mx = Math.max(mx, arr[i + 1])
            mn = Math.min(mn, arr[i])
        }
        else{
            mx = Math.max(mx, arr[i])
            mn = Math.min(mn, arr[i + 1])
        }
             
        // Increment the index by 2 as two
        // elements are processed in loop
        i += 2
    }
     
    return [mx, mn]
}
     
// Driver Code
     
let arr = [1000, 11, 445, 1, 330, 3000]
let mx = getMinMax(arr)[0]
let mn = getMinMax(arr)[1]
document.write("Minimum element is", mn,"</br>")
document.write("Maximum element is", mx,"</br>")
     
// This code is contributed by shinjanpatra
 
</script>

Producción: 

Minimum element is 1
Maximum element is 3000

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(1) ya que no se necesitaba espacio extra.

Número total de comparaciones: Diferente para n pares e impares, ver a continuación: 

       If n is odd:    3*(n-1)/2  
       If n is even:   1 Initial comparison for initializing min and max, 
                           and 3(n-2)/2 comparisons for rest of the elements  
                      =  1 + 3*(n-2)/2 = 3n/2 -2

Los enfoques segundo y tercero hacen el mismo número de comparaciones cuando n es una potencia de 2. 
En general, el método 3 parece ser el mejor.
Escriba comentarios si encuentra algún error en los programas/algoritmos anteriores o una mejor manera de resolver el mismo problema.
 

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *