Reorganizar array para encontrar K usando el algoritmo de búsqueda binaria sin ordenar

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: 

  1. Se puede encontrar un número entero K en una array ordenada arr[] usando el algoritmo de búsqueda binaria de la siguiente manera :
    1. Inicialmente, L = 0 y R = N-1.
    2. Mientras que L es menor o igual que R :
      1. Encuentre el punto medio del rango actual [L, R] como mid = (L+R)/2.
      2. Si arr[mid] es igual a K , devuelve verdadero .
      3. 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 .
      4. 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.
    3. Si no se encuentra K , devuelve false .
  2. 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.
  3. 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:
    1. 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 .
    2. 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 .
  4. Por tanto, desde arriba, se puede observar que, para ir el índice X , desde una posición mid , hay dos casos:
    1. 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 .
    2. 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 mid es mayor que K , haga lo siguiente:
    • 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *