Buscar un elemento en un Mountain Array

Dada una array de montaña arr[] y un entero X , la tarea es encontrar el índice más pequeño de X en la array dada. Si no se encuentra dicho índice, imprima -1 .

Ejemplos:

Entrada: arr = {1, 2, 3, 4, 5, 3, 1}, X = 3
Salida: 2
Explicación: 
El índice más pequeño de X(= 3) en la array es 2. 
Por lo tanto, la salida requerida es 2 .

Entrada: arr[] = {0, 1, 2, 4, 2, 1}, X = 3
Salida: -1
Explicación: Dado que 3 no existe en la array, la salida requerida es -1.

Enfoque ingenuo: el enfoque más simple es recorrer la array y verificar si el elemento en el índice actual es igual a X o no. Si se encuentra que es cierto, imprima ese índice. 

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Enfoque eficiente: la idea óptima para resolver este problema es utilizar la búsqueda binaria . Siga los pasos a continuación para resolver este problema:

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

C++

// CPP program for the above approach
#include<bits/stdc++.h>
using namespace std;
 
// Function to find the index of
// the peak element in the array
int findPeak(vector<int> arr)
{
 
  // Stores left most index in which
  // the peak element can be found
  int left = 0;
 
  // Stores right most index in which
  // the peak element can be found
  int right = arr.size() - 1;
  while (left < right)
  {
 
    // Stores mid of left and right
    int mid = left + (right - left) / 2;
 
    // If element at mid is less than
    // element at (mid + 1)
    if (arr[mid] < arr[mid + 1])
    {
 
      // Update left
      left = mid + 1;
    }
    else
    {
 
      // Update right
      right = mid;
    }
  }
  return left;
}
 
// Function to perform binary search in an
// a subarray if elements of the subarray
// are in an ascending order
int BS(int X, int left, int right,
       vector<int> arr)
{
  while (left <= right)
  {
 
    // Stores mid of left and right
    int mid = left + (right - left) / 2;
 
    // If X found at mid
    if (arr[mid] == X)
    {
      return mid;
    }
 
    // If X is greater than mid
    else if (X > arr[mid])
    {
 
      // Update left
      left = mid + 1;
    }
 
    else
    {
 
      // Update right
      right = mid - 1;
    }
  }
  return -1;
}
 
// Function to perform binary search in an
// a subarray if elements of the subarray
// are in an ascending order
int reverseBS(int X, int left, int right, vector<int> arr)
{
  while (left <= right)
  {
 
    // Stores mid of left and right
    int mid = left + (right - left) / 2;
 
    // If X found at mid
    if (arr[mid] == X)
    {
      return mid;
    }
 
    else if (X > arr[mid])
    {
 
      // Update right
      right = mid - 1;
    }
    else
    {
 
      // Update left
      left = mid + 1;
    }
  }
  return -1;
}
 
// Function to find the smallest index of X
void findInMA(int X, vector<int> mountainArr)
{
 
  // Stores index of peak element in array
  int peakIndex = findPeak(mountainArr);
 
  // Stores index of X in the array
  int res = -1;
 
  // If X greater than or equal to first element
  // of array and less than the peak element
  if (X >= mountainArr[0] && X <= mountainArr[peakIndex])
  {
 
    // Update res
    res = BS(X, 0, peakIndex, mountainArr);
  }
 
  // If element not found on
  // left side of peak element
  if (res == -1)
  {
 
    // Update res
    res = reverseBS(X, peakIndex + 1,
                    mountainArr.size() - 1,
                    mountainArr);
  }
 
  // Print res
  cout<<res<<endl;
}
 
// Driver Code
int main()
{
 
  // Given X
  int X = 3;
 
  // Given array
  vector<int> list{1, 2, 3, 4, 5, 3, 1};
 
  // Function Call
  findInMA(X, list);
}
 
// This code is contributed by bgangwar59.

Java

// Java program for the above approach
 
import java.io.*;
import java.util.*;
 
class GFG {
 
    // Function to find the index of
    // the peak element in the array
    public static int findPeak(
        ArrayList<Integer> arr)
    {
 
        // Stores left most index in which
        // the peak element can be found
        int left = 0;
 
        // Stores right most index in which
        // the peak element can be found
        int right = arr.size() - 1;
 
        while (left < right) {
 
            // Stores mid of left and right
            int mid = left + (right - left) / 2;
 
            // If element at mid is less than
            // element at (mid + 1)
            if (arr.get(mid) < arr.get(mid + 1)) {
 
                // Update left
                left = mid + 1;
            }
            else {
 
                // Update right
                right = mid;
            }
        }
 
        return left;
    }
 
    // Function to perform binary search in an
    // a subarray if elements of the subarray
    // are in an ascending order
    static int BS(int X, int left, int right,
                  ArrayList<Integer> arr)
    {
 
        while (left <= right) {
 
            // Stores mid of left and right
            int mid = left + (right - left) / 2;
 
            // If X found at mid
            if (arr.get(mid) == X) {
                return mid;
            }
 
            // If X is greater than mid
            else if (X > arr.get(mid)) {
 
                // Update left
                left = mid + 1;
            }
 
            else {
 
                // Update right
                right = mid - 1;
            }
        }
        return -1;
    }
 
    // Function to perform binary search in an
    // a subarray if elements of the subarray
    // are in an ascending order
    static int reverseBS(int X, int left, int right,
                         ArrayList<Integer> arr)
    {
        while (left <= right) {
 
            // Stores mid of left and right
            int mid = left + (right - left) / 2;
 
            // If X found at mid
            if (arr.get(mid) == X) {
                return mid;
            }
 
            else if (X > arr.get(mid)) {
 
                // Update right
                right = mid - 1;
            }
            else {
 
                // Update left
                left = mid + 1;
            }
        }
        return -1;
    }
 
    // Function to find the smallest index of X
    static void findInMA(int X,
                         ArrayList<Integer> mountainArr)
    {
 
        // Stores index of peak element in array
        int peakIndex = findPeak(mountainArr);
 
        // Stores index of X in the array
        int res = -1;
 
        // If X greater than or equal to first element
        // of array and less than the peak element
        if (X >= mountainArr.get(0)
            && X <= mountainArr.get(peakIndex)) {
 
            // Update res
            res = BS(X, 0, peakIndex, mountainArr);
        }
 
        // If element not found on
        // left side of peak element
        if (res == -1) {
 
            // Update res
            res = reverseBS(X, peakIndex + 1,
                            mountainArr.size() - 1,
                            mountainArr);
        }
 
        // Print res
        System.out.println(res);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        // Given X
        int X = 3;
 
        // Given array
        ArrayList<Integer> list = new ArrayList<>(
            Arrays.asList(1, 2, 3, 4, 5, 3, 1));
 
        // Function Call
        findInMA(X, list);
    }
}

Python3

# Python3 program for the above approach
 
# Function to find the index of
# the peak element in the array
def findPeak(arr):
     
    # Stores left most index in which
    # the peak element can be found
    left = 0
 
    # Stores right most index in which
    # the peak element can be found
    right = len(arr) - 1
 
    while (left < right):
 
        # Stores mid of left and right
        mid = left + (right - left) // 2
 
        # If element at mid is less than
        # element at(mid + 1)
        if (arr[mid] < arr[(mid + 1)]):
 
            # Update left
            left = mid + 1
 
        else:
 
            # Update right
            right = mid
 
    return left
 
# Function to perform binary search in an
# a subarray if elements of the subarray
# are in an ascending order
def BS(X, left, right, arr):
     
    while (left <= right):
 
        # Stores mid of left and right
        mid = left + (right - left) // 2
 
        # If X found at mid
        if (arr[mid] == X):
            return mid
 
        # If X is greater than mid
        elif (X > arr[mid]):
 
            # Update left
            left = mid + 1
 
        else:
 
            # Update right
            right = mid - 1
 
    return -1
 
# Function to perform binary search in an
# a subarray if elements of the subarray
# are in an ascending order
def reverseBS(X, left, right, arr):
     
    while (left <= right):
 
        # Stores mid of left and right
        mid = left + (right - left) // 2
 
        # If X found at mid
        if (arr[mid] == X):
            return mid
 
        elif (X > arr[mid]):
 
            # Update right
            right = mid - 1
 
        else:
             
            # Update left
            left = mid + 1
             
    return -1
 
# Function to find the smallest index of X
def findInMA(X, mountainArr):
     
    # Stores index of peak element in array
    peakIndex = findPeak(mountainArr)
 
    # Stores index of X in the array
    res = -1
 
    # If X greater than or equal to first element
    # of array and less than the peak element
    if (X >= mountainArr[0] and
        X <= mountainArr[peakIndex]):
 
        # Update res
        res = BS(X, 0, peakIndex, mountainArr)
 
    # If element not found on
    # left side of peak element
    if (res == -1):
 
        # Update res
        res = reverseBS(X, peakIndex + 1,
                        mountainArr.size() - 1,
                        mountainArr)
 
    # Print res
    print(res)
 
# Driver Code
if __name__ == "__main__":
 
    # Given X
    X = 3
 
    # Given array
    arr = [ 1, 2, 3, 4, 5, 3, 1 ]
 
    # Function Call
    findInMA(X, arr)
 
# This code is contributed by chitranayal

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
using System.Linq;
class GFG
{
 
    // Function to find the index of
    // the peak element in the array
    public static int findPeak(List<int> arr)
    {
 
        // Stores left most index in which
        // the peak element can be found
        int left = 0;
 
        // Stores right most index in which
        // the peak element can be found
        int right = arr.Count - 1;
 
        while (left < right)
        {
 
            // Stores mid of left and right
            int mid = left + (right - left) / 2;
 
            // If element at mid is less than
            // element at (mid + 1)
            if (arr[mid] < arr[(mid + 1)])
            {
 
                // Update left
                left = mid + 1;
            }
            else
            {
 
                // Update right
                right = mid;
            }
        }
 
        return left;
    }
 
    // Function to perform binary search in an
    // a subarray if elements of the subarray
    // are in an ascending order
    static int BS(int X, int left, int right,
                List<int> arr)
    {
 
        while (left <= right)
        {
 
            // Stores mid of left and right
            int mid = left + (right - left) / 2;
 
            // If X found at mid
            if (arr[(mid)] == X)
            {
                return mid;
            }
 
            // If X is greater than mid
            else if (X > arr[mid])
            {
 
                // Update left
                left = mid + 1;
            }
 
            else
            {
 
                // Update right
                right = mid - 1;
            }
        }
        return -1;
    }
 
    // Function to perform binary search in an
    // a subarray if elements of the subarray
    // are in an ascending order
    static int reverseBS(int X, int left, int right,
                         List<int> arr)
    {
        while (left <= right)
        {
 
            // Stores mid of left and right
            int mid = left + (right - left) / 2;
 
            // If X found at mid
            if (arr[mid] == X)
            {
                return mid;
            }
 
            else if (X > arr[mid])
            {
 
                // Update right
                right = mid - 1;
            }
            else
            {
 
                // Update left
                left = mid + 1;
            }
        }
        return -1;
    }
 
    // Function to find the smallest index of X
    static void findInMA(int X,
                         List<int> mountainArr)
    {
 
        // Stores index of peak element in array
        int peakIndex = findPeak(mountainArr);
 
        // Stores index of X in the array
        int res = -1;
 
        // If X greater than or equal to first element
        // of array and less than the peak element
        if (X >= mountainArr[0]
            && X <= mountainArr[peakIndex])
        {
 
            // Update res
            res = BS(X, 0, peakIndex, mountainArr);
        }
 
        // If element not found on
        // left side of peak element
        if (res == -1)
        {
 
            // Update res
            res = reverseBS(X, peakIndex + 1,
                            mountainArr.Count - 1,
                            mountainArr);
        }
 
        // Print res
        Console.WriteLine(res);
    }
 
    // Driver Code
    public static void Main( )
    {
 
        // Given X
        int X = 3;
 
        // Given array
        List<int> list =  new List<int>(){1, 2, 3, 4, 5, 3, 1};
 
        // Function Call
        findInMA(X, list);
    }
}
 
// This code is contributed by code_hunt.

Javascript

<script>
 
// Javascript program for the above approach
 
// Function to find the index of
// the peak element in the array
function findPeak(arr)
{
 
  // Stores left most index in which
  // the peak element can be found
  var left = 0;
 
  // Stores right most index in which
  // the peak element can be found
  var right = arr.length - 1;
  while (left < right)
  {
 
    // Stores mid of left and right
    var mid = left + parseInt((right - left) / 2);
 
    // If element at mid is less than
    // element at (mid + 1)
    if (arr[mid] < arr[mid + 1])
    {
 
      // Update left
      left = mid + 1;
    }
    else
    {
 
      // Update right
      right = mid;
    }
  }
  return left;
}
 
// Function to perform binary search in an
// a subarray if elements of the subarray
// are in an ascending order
function BS(X, left, right, arr)
{
  while (left <= right)
  {
 
    // Stores mid of left and right
    var mid = left + parseInt((right - left) / 2);
 
    // If X found at mid
    if (arr[mid] == X)
    {
      return mid;
    }
 
    // If X is greater than mid
    else if (X > arr[mid])
    {
 
      // Update left
      left = mid + 1;
    }
 
    else
    {
 
      // Update right
      right = mid - 1;
    }
  }
  return -1;
}
 
// Function to perform binary search in an
// a subarray if elements of the subarray
// are in an ascending order
function reverseBS(X, left, right, arr)
{
  while (left <= right)
  {
 
    // Stores mid of left and right
    var mid = left + parseInt((right - left) / 2);
 
    // If X found at mid
    if (arr[mid] == X)
    {
      return mid;
    }
 
    else if (X > arr[mid])
    {
 
      // Update right
      right = mid - 1;
    }
    else
    {
 
      // Update left
      left = mid + 1;
    }
  }
  return -1;
}
 
// Function to find the smallest index of X
function findInMA(X, mountainArr)
{
 
  // Stores index of peak element in array
  var peakIndex = findPeak(mountainArr);
 
  // Stores index of X in the array
  var res = -1;
 
  // If X greater than or equal to first element
  // of array and less than the peak element
  if (X >= mountainArr[0] && X <= mountainArr[peakIndex])
  {
 
    // Update res
    res = BS(X, 0, peakIndex, mountainArr);
  }
 
  // If element not found on
  // left side of peak element
  if (res == -1)
  {
 
    // Update res
    res = reverseBS(X, peakIndex + 1,
                    mountainArr.length - 1,
                    mountainArr);
  }
 
  // Print res
  document.write( res + "<br>");
}
 
// Driver Code
// Given X
var X = 3;
// Given array
var list = [1, 2, 3, 4, 5, 3, 1];
// Function Call
findInMA(X, list);
 
</script>
Producción: 

2

 

Complejidad de tiempo: O(Log(N))
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por rohit2sahu 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 *