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>
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