Dada una array arr[] de tamaño N , la tarea es encontrar el recuento mínimo de elementos de la array encontrados aplicando la búsqueda binaria aleatoria para cada elemento de la array.
Ejemplos:
Entrada: arr[] = { 5, 4, 9 }
Salida: 2
Explicación:
Aplicación de la búsqueda binaria aleatoria de arr[0] en la array.
Inicialmente, el espacio de búsqueda es [0, 2]
Supongamos pivote = 1 y arr[pivot] < arr[0]. Por lo tanto, el nuevo espacio de búsqueda es [2, 2] y arr[0] no se encuentra en el espacio de búsqueda.
Para arr[1], el espacio de búsqueda es [0, 2].
Supongamos pivote = 0 y arr[pivot] > arr[0]. Por lo tanto, el nuevo espacio de búsqueda es [0, 0] y arr[1] no se encuentra en el espacio de búsqueda.
Para arr[2], el espacio de búsqueda es [0, 2].
Seleccionando cualquier elemento como pivote, se puede encontrar arr[2].Entrada: arr[] = { 1, 2, 3, 4 }
Salida: 4
Enfoque: la idea es contar los elementos de la array antes de que todos los elementos de la array sean más pequeños que él y después de lo cual todos sean más grandes que él . Siga los pasos a continuación para resolver el problema:
- Inicialice una array , diga más pequeñoDerecho[] para almacenar el elemento más pequeño en el lado derecho de cada elemento de la array.
- Recorra la array en reversa y actualice la derecha más pequeña [i] = min (la derecha más pequeña [ i + 1], arr [i]) .
- Recorra la array y almacene el elemento más grande en el lado izquierdo de cada elemento de la array y verifique si el elemento más grande en el lado izquierdo es menor que el elemento más pequeño en el lado derecho o no. Si se encuentra que es cierto, entonces incremente el conteo.
- Finalmente, imprima el conteo obtenido.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find minimum count of
// array elements found by repeatedly
// applying Randomized Binary Search
int getDefiniteFinds(vector<int>& arr)
{
// Stores count of array elements
int n = arr.size();
// smallestRight[i]: Stores the smallest
// array element on the right side of i
vector<int> smallestRight(n + 1);
// Update smallestRight[0]
smallestRight[n] = INT_MAX;
// Traverse the array from right to left
for (int i = n - 1; i >= 0; i--) {
// Update smallestRight[i]
smallestRight[i]
= min(smallestRight[i + 1], arr[i]);
}
// Stores the largest element
// upto i-th index
int mn = INT_MIN;
// Stores the minimum count of
// elements found by repeatedly
// applying Randomized Binary Search
int ans = 0;
for (int i = 0; i < n; i++) {
// If largest element on left side is
// less than smallest element on right side
if (mn < arr[i] and arr[i] < smallestRight[i + 1]) {
// Update ans
ans++;
}
// Update mn
mn = max(arr[i], mn);
}
return ans;
}
// Driver Code
int main()
{
// Given array
vector<int> arr = { 5, 4, 9 };
// Function Call
cout << getDefiniteFinds(arr) << endl;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG
{
// Function to find minimum count of
// array elements found by repeatedly
// applying Randomized Binary Search
static int getDefiniteFinds(int[] arr)
{
// Stores count of array elements
int n = arr.length;
// smallestRight[i]: Stores the smallest
// array element on the right side of i
int[] smallestRight = new int[n + 1];
// Update smallestRight[0]
smallestRight[n] = Integer.MAX_VALUE;
// Traverse the array from right to left
for (int i = n - 1; i >= 0; i--)
{
// Update smallestRight[i]
smallestRight[i]
= Math.min(smallestRight[i + 1], arr[i]);
}
// Stores the largest element
// upto i-th index
int mn = Integer.MIN_VALUE;
// Stores the minimum count of
// elements found by repeatedly
// applying Randomized Binary Search
int ans = 0;
for (int i = 0; i < n; i++)
{
// If largest element on left side is
// less than smallest element on right side
if (mn < arr[i]
&& arr[i] < smallestRight[i + 1])
{
// Update ans
ans++;
}
// Update mn
mn = Math.max(arr[i], mn);
}
return ans;
}
// Driver Code
public static void main(String[] args)
{
// Given array
int[] arr = new int[] { 5, 4, 9 };
// Function Call
System.out.println(getDefiniteFinds(arr));
}
}
// This code is contributed by Dharanendra L V
Python3
# Python3 program for the above approach import sys # Function to find minimum count of # array elements found by repeatedly # applying Randomized Binary Search def getDefiniteFinds(arr): # Stores count of array elements n = len(arr) # smallestRight[i]: Stores the smallest # array element on the right side of i smallestRight = [0] * (n + 1) # Update smallestRight[0] smallestRight[n] = sys.maxsize # Traverse the array from right to left for i in range(n - 1, -1, -1): # Update smallestRight[i] smallestRight[i] = min( smallestRight[i + 1], arr[i]) # Stores the largest element # upto i-th index mn = -sys.maxsize - 1 # Stores the minimum count of # elements found by repeatedly # applying Randomized Binary Search ans = 0 for i in range(n): # If largest element on left side is # less than smallest element on right side if (mn < arr[i] and arr[i] < smallestRight[i + 1]): # Update ans ans += 1 # Update mn mn = max(arr[i], mn) return ans # Driver Code # Given array arr = [ 5, 4, 9 ] # Function Call print(getDefiniteFinds(arr)) # This code is contributed by susmitakundugoaldanga
C#
// C# program for the above approach
using System;
class GFG
{
// Function to find minimum count of
// array elements found by repeatedly
// applying Randomized Binary Search
static int getDefiniteFinds(int[] arr)
{
// Stores count of array elements
int n = arr.Length;
// smallestRight[i]: Stores the smallest
// array element on the right side of i
int[] smallestRight = new int[n + 1];
// Update smallestRight[0]
smallestRight[n] = Int32.MaxValue;
// Traverse the array from right to left
for (int i = n - 1; i >= 0; i--)
{
// Update smallestRight[i]
smallestRight[i]
= Math.Min(smallestRight[i + 1], arr[i]);
}
// Stores the largest element
// upto i-th index
int mn = Int32.MinValue;
// Stores the minimum count of
// elements found by repeatedly
// applying Randomized Binary Search
int ans = 0;
for (int i = 0; i < n; i++)
{
// If largest element on left side is
// less than smallest element on right side
if (mn < arr[i]
&& arr[i] < smallestRight[i + 1])
{
// Update ans
ans++;
}
// Update mn
mn = Math.Max(arr[i], mn);
}
return ans;
}
// Driver Code
static public void Main()
{
// Given array
int[] arr = new int[] { 5, 4, 9 };
// Function Call
Console.WriteLine(getDefiniteFinds(arr));
}
}
// This code is contributed by Dharanendra L V
Javascript
<script>
// javascript program of the above approach
// Function to find minimum count of
// array elements found by repeatedly
// applying Randomized Binary Search
function getDefiniteFinds(arr)
{
// Stores count of array elements
let n = arr.length;
// smallestRight[i]: Stores the smallest
// array element on the right side of i
let smallestRight = new Array(n+1).fill(0);
// Update smallestRight[0]
smallestRight[n] = Number.MAX_VALUE;
// Traverse the array from right to left
for (let i = n - 1; i >= 0; i--)
{
// Update smallestRight[i]
smallestRight[i]
= Math.min(smallestRight[i + 1], arr[i]);
}
// Stores the largest element
// upto i-th index
let mn = Number.MIN_VALUE;
// Stores the minimum count of
// elements found by repeatedly
// applying Randomized Binary Search
let ans = 0;
for (let i = 0; i < n; i++)
{
// If largest element on left side is
// less than smallest element on right side
if (mn < arr[i]
&& arr[i] < smallestRight[i + 1])
{
// Update ans
ans++;
}
// Update mn
mn = Math.max(arr[i], mn);
}
return ans;
}
// Driver Code
// Given array
let arr = [ 5, 4, 9 ];
// Function Call
document.write(getDefiniteFinds(arr));
// This code is contributed by chinmoy1997pal.
</script>
Producción:
1
Complejidad temporal: O(N)
Espacio auxiliar: O(N)