Dada una array , arr[] de N enteros distintos y un entero K , la tarea es reorganizar la array dada de tal manera que K se pueda encontrar con la ayuda del algoritmo de búsqueda binaria en la array reorganizada. Tenga en cuenta que la array no debe ordenarse.
Ejemplos:
Entrada : arr[] = {10, 7, 2, 5, 3, 8}, K = 7
Salida: 3 7 8 5 2 10
Explicación: encontrar K en la array de salida {3, 7, 8, 5, 2, 10 } utilizando la búsqueda binaria
: inicialmente, izquierda (L) = 0, derecha (R) = 5, mitad = 2, es decir, 8 (no igual a K)
, ya que 8 > K, por lo tanto, izquierda (L) = 0, derecha (R ) = 1, mid = 0, es decir, 3 (no igual a K)
— dado que 3 < K, por lo tanto, izquierda (L) = 1, derecha (R) = 1, mid = 1, es decir, 7 (que es igual a K)
Por lo tanto, K se puede encontrar en la array de salida utilizando la búsqueda binaria, incluso la array no está ordenada.
Entrada : arr[] = {10, 7, 2, 5, 8, 6}, K = 6
Salida: 8 7 5 10 2 6
Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:
- Se puede encontrar un número entero K en una array ordenada arr[] usando el algoritmo de búsqueda binaria de la siguiente manera :
- Inicialmente, L = 0 y R = N-1.
- Mientras que L es menor o igual que R :
- Encuentre el punto medio del rango actual [L, R] como mid = (L+R)/2.
- Si arr[mid] es igual a K , devuelve verdadero .
- De lo contrario, si arr[mid] es mayor que K , entonces actualice R a mid-1 , es decir, se omiten todos los elementos a la derecha de mid .
- De lo contrario, si arr[mid] es menor que K , actualice L a mid+1 , es decir, todos los elementos que quedan de mid se omiten.
- Si no se encuentra K , devuelve false .
- El algoritmo de búsqueda binaria puede fallar en arrays no ordenadas porque la array no cumple con los criterios de que la array aumente o disminuya de forma monótona. Pero, a veces, el algoritmo de búsqueda binaria también puede funcionar en arrays no ordenadas.
- Por ejemplo, suponga que la array dada, arr[] es igual a {2, 1, 5, 4, 3} y K es igual a 2 . Entonces el algoritmo funciona como:
- En la primera iteración:
- L=0 y R= 4 , por lo tanto mid = (4+0)/2 =2.
- El arr[2] (=5) es mayor que 2 , así que asigne mid-1 a R. Ahora R se convierte en 1 .
- En la segunda iteración:
- L=0 y R= 1 , por lo tanto mid = (1+0)/2 =0.
- El arr[0] (=2) es igual a 2. Por lo tanto, devuelve verdadero .
- Por tanto, desde arriba, se puede observar que, para ir el índice X , desde una posición mid , hay dos casos:
- Si mid es menor que X , entonces arr[mid] tiene que ser menor que arr[X] para moverse hacia el índice X , que se encuentra en el lado derecho de mid .
- De lo contrario, si mid es mayor que X entonces arr[mid] tiene que ser mayor que arr[X] , para moverse hacia el índice X , que se encuentra en el lado izquierdo de mid
Siga los pasos a continuación para resolver el problema:
- Inicialice una array , digamos ans[] con todos los elementos de la array como -1 para almacenar la array reorganizada.
- Además, inicialice dos vectores , digamos más pequeños y más grandes , para almacenar los elementos más pequeños y más grandes que K .
- Recorre la array, arr[] y empuja el elemento actual a un valor más pequeño si es menor que K . De lo contrario, introdúzcalo en mayor si es mayor que K .
- Encuentre el índice del elemento K en la array arr[] y luego asígnele el valor a K .
- Inicialice dos variables, digamos bajo como 0 y alto como N-1 , para realizar una búsqueda binaria.
- Iterar hasta que low sea menor o igual que high y realizar los siguientes pasos:
- Encuentra la mitad del rango actual [bajo, alto] y guárdalo en una variable, digamos mid .
- Si mid es menor que K , haga lo siguiente:
- Si small.size() es 0 , imprima » -1 » y regrese.
- De lo contrario, asigne el último elemento del vector , más pequeño a ans[mid] , y luego extraiga el último elemento de más pequeño .
- Si mid es mayor que K , haga lo siguiente:
- Si mayor.tamaño() es 0 , imprima » -1 » y regrese.
- De lo contrario, asigne el último elemento del vector , mayor a ans[mid] , y luego extraiga el último elemento de mayor .
- Si mid es igual a K , entonces asigne arr[K] a ans[mid] y luego rompa .
- Después de completar los pasos anteriores, recorra la array , ans[] y si el elemento actual es » -1 «, es decir, no está lleno, asígnele cualquier elemento no utilizado.
- Finalmente, imprima la array ans[] como la array reorganizada.
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 rearrange the array
void Rearrange(int arr[], int K, int N)
{
// Stores the rearranged array
int ans[N + 1];
// Stores whether the arrangement
// is possible or not
int f = -1;
for (int i = 0; i < N; i++) {
ans[i] = -1;
}
// Update K with the position of K
K = find(arr, arr + N, K) - arr;
// Stores all elements lesser than
// and greater than in vector smaller
// and greater respectively
vector<int> smaller, greater;
// Traverse the array arr[]
for (int i = 0; i < N; i++) {
// If arr[i] is less than arr[K]
if (arr[i] < arr[K])
smaller.push_back(arr[i]);
// Else
else if (arr[i] > arr[K])
greater.push_back(arr[i]);
}
int low = 0, high = N - 1;
// Iterate until low is less than or
// equal to high
while (low <= high) {
// Stores mid point
int mid = (low + high) / 2;
// If mid is equal to K
if (mid == K) {
ans[mid] = arr[K];
f = 1;
break;
}
// If mid is less than K
else if (mid < K) {
if (smaller.size() == 0) {
break;
}
ans[mid] = smaller.back();
smaller.pop_back();
low = mid + 1;
}
// If mid is greater than K
else {
if (greater.size() == 0) {
break;
}
ans[mid] = greater.back();
greater.pop_back();
high = mid - 1;
}
}
// If f is -1
if (f == -1) {
cout << -1 << endl;
return;
}
// Iterate in the range [1, N]
for (int i = 0; i < N; i++) {
// If ans[i] is equal to -1
if (ans[i] == -1) {
if (smaller.size()) {
ans[i] = smaller.back();
smaller.pop_back();
}
else if (greater.size()) {
ans[i] = greater.back();
greater.pop_back();
}
}
}
// Print the rearranged array
for (int i = 0; i < N; i++)
cout << ans[i] << " ";
cout << endl;
}
// Driver Code
int main()
{
// Input
int arr[] = { 10, 7, 2, 5, 3, 8 };
int K = 7;
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
Rearrange(arr, K, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
public class GFG
{
// Function to rearrange the array
static void Rearrange(int arr[], int K, int N)
{
// Stores the rearranged array
int ans[] = new int[N + 1];
// Stores whether the arrangement
// is possible or not
int f = -1;
for (int i = 0; i < N; i++) {
ans[i] = -1;
}
// Update K with the position of K
for (int i = 0; i < arr.length; i++)
{
if (arr[i] == K)
{
K = i;
break;
}
}
// Stores all elements lesser than
// and greater than in vector smaller
// and greater respectively
Vector<Integer> smaller = new Vector<Integer>();
Vector<Integer> greater = new Vector<Integer>();
// Traverse the array arr[]
for (int i = 0; i < N; i++) {
// If arr[i] is less than arr[K]
if (arr[i] < arr[K])
smaller.add(arr[i]);
// Else
else if (arr[i] > arr[K])
greater.add(arr[i]);
}
int low = 0, high = N - 1;
// Iterate until low is less than or
// equal to high
while (low <= high) {
// Stores mid point
int mid = (low + high) / 2;
// If mid is equal to K
if (mid == K) {
ans[mid] = arr[K];
f = 1;
break;
}
// If mid is less than K
else if (mid < K) {
if (smaller.size() == 0) {
break;
}
ans[mid] = smaller.lastElement();
smaller.remove(smaller.size()-1);
low = mid + 1;
}
// If mid is greater than K
else {
if (greater.size() == 0) {
break;
}
ans[mid] = greater.lastElement();
greater.remove(greater.size()-1);
high = mid - 1;
}
}
// If f is -1
if (f == -1) {
System.out.println(-1 );
return;
}
// Iterate in the range [1, N]
for (int i = 0; i < N; i++) {
// If ans[i] is equal to -1
if (ans[i] == -1) {
if (smaller.size()>0) {
ans[i] = smaller.lastElement();
smaller.remove(smaller.size()-1);
}
else if (greater.size()>0) {
ans[i] = greater.lastElement();
greater.remove(greater.size()-1);
}
}
}
// Print the rearranged array
for (int i = 0; i < N; i++)
System.out.print(ans[i] +" ");
System.out.println();
}
// Driver code
public static void main(String args[])
{
// Input
int arr[] = { 10, 7, 2, 5, 3, 8 };
int K = 7;
int N = arr.length;
// Function Call
Rearrange(arr, K, N);
}
}
// This code is contributed by SoumikMondal
Python3
# Python 3 program for the above approach # Function to rearrange the array def Rearrange(arr, K, N): # Stores the rearranged array ans = [0]*(N + 1) # Stores whether the arrangement # is possible or not f = -1 for i in range(N): ans[i] = -1 # Update K with the position of K K = arr.index(K) # Stores all elements lesser than # and greater than in vector smaller # and greater respectively smaller = [] greater = [] # Traverse the array arr[] for i in range(N): # If arr[i] is less than arr[K] if (arr[i] < arr[K]): smaller.append(arr[i]) # Else elif (arr[i] > arr[K]): greater.append(arr[i]) low = 0 high = N - 1 # Iterate until low is less than or # equal to high while (low <= high): # Stores mid point mid = (low + high) // 2 # If mid is equal to K if (mid == K): ans[mid] = arr[K] f = 1 break # If mid is less than K elif (mid < K): if (len(smaller) == 0): break ans[mid] = smaller[-1] smaller.pop() low = mid + 1 # If mid is greater than K else: if (len(greater) == 0): break ans[mid] = greater[-1] greater.pop() high = mid - 1 # If f is -1 if (f == -1): print(-1) return # Iterate in the range [1, N] for i in range(N): # If ans[i] is equal to -1 if (ans[i] == -1): if (len(smaller)): ans[i] = smaller[-1] smaller.pop() elif (len(greater)): ans[i] = greater[-1] greater.pop() # Print the rearranged array for i in range(N): print(ans[i], end=" ") print() # Driver Code if __name__ == "__main__": # Input arr = [10, 7, 2, 5, 3, 8] K = 7 N = len(arr) # Function Call Rearrange(arr, K, N) # This code is contributed by ukasp.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG
{
// Function to rearrange the array
static void Rearrange(int []arr, int K, int N)
{
// Stores the rearranged array
int []ans = new int[N + 1];
// Stores whether the arrangement
// is possible or not
int f = -1;
for (int i = 0; i < N; i++) {
ans[i] = -1;
}
// Update K with the position of K
for (int i = 0; i < arr.Length; i++)
{
if (arr[i] == K)
{
K = i;
break;
}
}
// Stores all elements lesser than
// and greater than in vector smaller
// and greater respectively
List<int> smaller = new List<int>();
List<int> greater = new List<int>();
// Traverse the array []arr
for (int i = 0; i < N; i++) {
// If arr[i] is less than arr[K]
if (arr[i] < arr[K])
smaller.Add(arr[i]);
// Else
else if (arr[i] > arr[K])
greater.Add(arr[i]);
}
int low = 0, high = N - 1;
// Iterate until low is less than or
// equal to high
while (low <= high) {
// Stores mid point
int mid = (low + high) / 2;
// If mid is equal to K
if (mid == K) {
ans[mid] = arr[K];
f = 1;
break;
}
// If mid is less than K
else if (mid < K) {
if (smaller.Count == 0) {
break;
}
ans[mid] = smaller[smaller.Count-1];
smaller.RemoveAt(smaller.Count-1);
low = mid + 1;
}
// If mid is greater than K
else {
if (greater.Count == 0) {
break;
}
ans[mid] = greater[greater.Count-1];
greater.RemoveAt(greater.Count-1);
high = mid - 1;
}
}
// If f is -1
if (f == -1) {
Console.WriteLine(-1 );
return;
}
// Iterate in the range [1, N]
for (int i = 0; i < N; i++) {
// If ans[i] is equal to -1
if (ans[i] == -1) {
if (smaller.Count>0) {
ans[i] = smaller[smaller.Count-1];
smaller.RemoveAt(smaller.Count-1);
}
else if (greater.Count>0) {
ans[i] = greater[greater.Count-1];
greater.RemoveAt(greater.Count-1);
}
}
}
// Print the rearranged array
for (int i = 0; i < N; i++)
Console.Write(ans[i] +" ");
Console.WriteLine();
}
// Driver code
public static void Main(String []args)
{
// Input
int []arr = { 10, 7, 2, 5, 3, 8 };
int K = 7;
int N = arr.Length;
// Function Call
Rearrange(arr, K, N);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// JavaScript program for the above approach
// Function to rearrange the array
function Rearrange(arr, K, N)
{
// Stores the rearranged array
let ans = new Array(N + 1);
// Stores whether the arrangement
// is possible or not
let f = -1;
for (let i = 0; i < N; i++) {
ans[i] = -1;
}
// Update K with the position of K
for (let i = 0; i < arr.length; i++) {
if (arr[i] == K) {
K = i;
break;
}
}
// Stores all elements lesser than
// and greater than in vector smaller
// and greater respectively
let smaller = [];
let greater = [];
// Traverse the array arr[]
for (let i = 0; i < N; i++) {
// If arr[i] is less than arr[K]
if (arr[i] < arr[K])
smaller.push(arr[i]);
// Else
else if (arr[i] > arr[K])
greater.push(arr[i]);
}
let low = 0, high = N - 1;
// Iterate until low is less than or
// equal to high
while (low <= high) {
// Stores mid point
let mid = Math.floor((low + high) / 2);
// If mid is equal to K
if (mid == K) {
ans[mid] = arr[K];
f = 1;
break;
}
// If mid is less than K
else if (mid < K) {
if (smaller.length == 0) {
break;
}
ans[mid] = smaller[smaller.length - 1];
smaller.pop();
low = mid + 1;
}
// If mid is greater than K
else {
if (greater.length == 0) {
break;
}
ans[mid] = greater[greater.length - 1];
greater.pop();
high = mid - 1;
}
}
// If f is -1
if (f == -1) {
document.write(-1);
return;
}
// Iterate in the range [1, N]
for (let i = 0; i < N; i++) {
// If ans[i] is equal to -1
if (ans[i] == -1) {
if (smaller.length != 0) {
ans[i] = smaller[smaller.length - 1];
smaller.pop();
}
else if (greater.length != 0) {
ans[i] = greater[greater.length - 1];
greater.pop;
}
}
}
// Print the rearranged array
for (let i = 0; i < N; i++)
document.write(ans[i] + " ");
document.write("<br>")
}
// Driver Code
// Input
let arr = [10, 7, 2, 5, 3, 8];
let K = 7;
let N = arr.length;
// Function Call
Rearrange(arr, K, N);
// This code is contributed by Potta Lokesh
</script>
Producción
3 7 8 5 2 10
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por swatijha0908 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA