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:
- Encuentre el índice de pico de la array de montaña .
- Sobre la base del índice de pico obtenido, la array de partición en dos partes. Primero busca su lado izquierdo usando la búsqueda binaria , seguido por su lado derecho. Se sabe que el lado izquierdo del elemento pico se clasifica en orden ascendente y el lado derecho se clasifica en orden descendente .
- Busque en la array de montaña izquierda.
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