Compruebe si una array está ordenada y girada mediante la búsqueda binaria

Posted on by Rudeus Greyrat

Requisito previo: verificar si una array se ordena y gira mediante la búsqueda lineal
Dada una array arr[] de N enteros distintos, la tarea es verificar si esta array se ordena cuando se gira en sentido contrario a las agujas del reloj. Una array ordenada no se considera ordenada y rotada, es decir, debe haber al menos una rotación.

Ejemplos: 

Entrada: arr[] = { 3, 4, 5, 1, 2 } 
Salida: verdadero 
Explicación: 
array ordenada: {1, 2, 3, 4, 5}. 
Girando esta array ordenada en el sentido de las agujas 
del reloj 3 posiciones, obtenemos: { 3, 4, 5, 1, 2}

Entrada: arr[] = {7, 9, 11, 12, 5} 
Salida: verdadero

Entrada: arr[] = {1, 2, 3} 
Salida: falso 

Enfoque: En este artículo ya se analizó un enfoque para resolver este problema mediante la búsqueda lineal . En este artículo, se menciona un enfoque que utiliza el concepto  de búsqueda binaria .

  • Para aplicar una búsqueda binaria , la array debe seguir un orden en el que, en cada iteración, se pueda eliminar la mitad de la array.
  • Por lo tanto, el orden seguido por una array ordenada y rotada es que todos los elementos a la izquierda del pivote (el punto en el que se rota la array) están en orden descendente y todos los elementos a la derecha del pivote estarían en orden descendente. estar en orden ascendente. 
    Esto se puede visualizar en la siguiente ilustración:
     

  • Por lo tanto, el pivote se puede encontrar utilizando la búsqueda binaria y la recursividad de la siguiente manera: 
    • Casos base: el caso base será cuando se haya encontrado el pivote o si no se puede encontrar el pivote en la array dada. El pivote no se puede encontrar cuando el índice derecho es menor que el índice izquierdo. -1 se devuelve en estos casos. Y cuando alto y bajo apuntan al mismo elemento, entonces el elemento bajo es el pivote y ese elemento se devuelve.
if (high < low)
     return -1;
if (high == low)
     return low;
  • Aparte de esto, otro caso base es cuando mid((low + high) / 2) es un pivote. El elemento en el medio se considera cuando ese elemento es menor que el elemento siguiente o mayor que el elemento anterior.
if (mid < high && arr[mid + 1] < arr[mid])
    return mid;
if (mid > low && arr[mid] < arr[mid - 1])
    return mid - 1;
  • Caso recursivo: cuando ninguno de los casos base satisface, entonces se debe tomar la decisión de ignorar la primera mitad o la segunda mitad. Esta decisión se toma comprobando si el elemento del primer índice (bajo) es mayor que el elemento del índice medio o no. Si es así, entonces el pivote seguramente se encuentra en la primera mitad. De lo contrario, el pivote se encuentra en la segunda mitad.
if (arr[low] > arr[mid]) 
    return findPivot(arr, low, mid - 1);    
else 
    return findPivot(arr, mid + 1, high);
  • Una vez que se encuentra el pivote, recorra hacia la izquierda de la array desde el pivote y verifique si todos los elementos están en orden descendente, o recorra hacia la derecha de la array y verifique si todos los elementos están en orden ascendente o no.

A continuación se muestra la implementación del enfoque anterior: 

C++

#include <bits/stdc++.h>
 
using namespace std;
 
// Function to return the
// index of the pivot
int findPivot(int arr[], int low, int high)
{
    // Base cases
    if (high < low)
        return -1;
    if (high == low)
        return low;
 
    int mid = (low + high) / 2;
    if (mid < high && arr[mid + 1] < arr[mid])
    {
        return mid;
    }
 
    // Check if element at (mid - 1) is pivot
    // Consider the cases like {4, 5, 1, 2, 3}
    if (mid > low && arr[mid] < arr[mid - 1])
    {
        return mid - 1;
    }
 
    // Decide whether we need to go to
    // the left half or the right half
    if (arr[low] > arr[mid])
    {
        return findPivot(arr, low, mid - 1);
    }
    else
    {
        return findPivot(arr, mid + 1, high);
    }
}
 
// Function to check if a given array
// is sorted rotated or not
bool isRotated(int arr[], int n)
{
    int l = 0;
    int r = n - 1;
    int pivot = -1;
    if (arr[l] > arr[r])
    {
        pivot = findPivot(arr, l, r);
        int temp=pivot;
        // To check if the elements to the left
        // of the pivot are in descending or not
        if (l < pivot)
        {
            while (pivot > l)
            {
                if (arr[pivot] < arr[pivot - 1])
                {
                    return false;
                }
                pivot--;
            }
        }
 
        // To check if the elements to the right
        // of the pivot are in ascending or not
        pivot=temp;
        if(pivot < r) {
            pivot++;
            while (pivot < r) {
                if (arr[pivot] > arr[pivot + 1]) {
                    return false;
                }
                pivot++;
            }
        }
 
        // If both of the above if is true
        // Then the array is sorted rotated
        return true;
    }
 
    // Else the array is not sorted rotated
    else {
        return false;
    }
}
 
// Driver code
int main()
{
    int arr[] = { 4, 5, 1, 3, 2 };
    if (isRotated(arr, 5)) cout<<"true";
    else
    cout<<"false";
    return 0;
}
 
// This code is contributed by mohit kumar 29

Java

// Java implementation of the above approach
 
class GFG {
 
    // Function to return the
    // index of the pivot
    static int findPivot(int arr[], int low, int high)
    {
        // Base cases
        if (high < low)
            return -1;
        if (high == low)
            return low;
 
        int mid = (low + high) / 2;
        if (mid < high && arr[mid + 1] < arr[mid]) {
            return mid;
        }
 
        // Check if element at (mid - 1) is pivot
        // Consider the cases like {4, 5, 1, 2, 3}
        if (mid > low && arr[mid] < arr[mid - 1]) {
            return mid - 1;
        }
 
        // Decide whether we need to go to
        // the left half or the right half
        if (arr[low] > arr[mid]) {
            return findPivot(arr, low, mid - 1);
        }
        else {
            return findPivot(arr, mid + 1, high);
        }
    }
 
    // Function to check if a given array
    // is sorted rotated or not
    public static boolean isRotated(int arr[], int n)
    {
        int l = 0;
        int r = n - 1;
        int pivot = -1;
        if (arr[l] > arr[r]) {
            pivot = findPivot(arr, l, r);
            int temp=pivot;
            // To check if the elements to the left
            // of the pivot are in descending or not
            if (l < pivot) {
                while (pivot > l) {
                    if (arr[pivot] < arr[pivot - 1]) {
                        return false;
                    }
                    pivot--;
                }
            }
 
            // To check if the elements to the right
            // of the pivot are in ascending or not
           
            pivot=temp;
            else {
                pivot++;
                while (pivot < r) {
                    if (arr[pivot] > arr[pivot + 1]) {
                        return false;
                    }
                    pivot++;
                }
            }
 
            // If any of the above if or else is true
            // Then the array is sorted rotated
            return true;
        }
 
        // Else the array is not sorted rotated
        else {
            return false;
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int arr[] = {  4, 5, 1, 3, 2 };
        System.out.println(isRotated(arr, 5));
    }
}

Python3

# Python3 implementation of the above approach
 
# Function to return the
# index of the pivot
def findPivot(arr, low, high) :
 
    # Base cases
    if (high < low) :
        return -1;
         
    if (high == low) :
        return low;
 
    mid = (low + high) // 2;
    if (mid < high and arr[mid + 1] < arr[mid]) :
     
        return mid;
 
    # Check if element at (mid - 1) is pivot
    # Consider the cases like {4, 5, 1, 2, 3}
    if (mid > low and arr[mid] < arr[mid - 1]) :
     
        return mid - 1;
     
    # Decide whether we need to go to
    # the left half or the right half
    if (arr[low] > arr[mid]) :
     
        return findPivot(arr, low, mid - 1);
     
    else :
     
        return findPivot(arr, mid + 1, high);
     
# Function to check if a given array
# is sorted rotated or not
def isRotated(arr, n) :
 
    l = 0;
    r = n - 1;
    pivot = -1;
    if (arr[l] > arr[r]) :
     
        pivot = findPivot(arr, l, r);
        temp = pivot
        # To check if the elements to the left
        # of the pivot are in descending or not
         
        if (l < pivot) :
         
            while (pivot > l) :
             
                if (arr[pivot] < arr[pivot - 1]) :
                 
                    return False;
                 
                pivot -= 1;
 
        # To check if the elements to the right
        # of the pivot are in ascending or not
         
        else :
            pivot=temp
            pivot += 1;
            while (pivot < r) :
                if (arr[pivot] > arr[pivot + 1]) :
                    return False;
                 
                pivot ++ 1;
     
        # If any of the above if or else is true
        # Then the array is sorted rotated
        return True;
 
    # Else the array is not sorted rotated
    else :
        return False;
 
 
# Driver code
if __name__ == "__main__" :
 
    arr = [ 3, 4, 5, 1, 2 ];
    if (isRotated(arr, 5)) :
        print("True");
    else :
        print("False");
 
# This code is contributed by Yash_R

C#

// C# implementation of the above approach
using System;
 
class GFG {
  
    // Function to return the
    // index of the pivot
    static int findPivot(int []arr, int low, int high)
    {
        // Base cases
        if (high < low)
            return -1;
        if (high == low)
            return low;
  
        int mid = (low + high) / 2;
        if (mid < high && arr[mid + 1] < arr[mid]) {
            return mid;
        }
  
        // Check if element at (mid - 1) is pivot
        // Consider the cases like {4, 5, 1, 2, 3}
        if (mid > low && arr[mid] < arr[mid - 1]) {
            return mid - 1;
        }
  
        // Decide whether we need to go to
        // the left half or the right half
        if (arr[low] > arr[mid]) {
            return findPivot(arr, low, mid - 1);
        }
        else {
            return findPivot(arr, mid + 1, high);
        }
    }
  
    // Function to check if a given array
    // is sorted rotated or not
    public static bool isRotated(int []arr, int n)
    {
        int l = 0;
        int r = n - 1;
        int pivot = -1;
        if (arr[l] > arr[r]) {
            pivot = findPivot(arr, l, r);
            int temp = pivot;
            // To check if the elements to the left
            // of the pivot are in descending or not
            if (l < pivot) {
                while (pivot > l) {
                    if (arr[pivot] < arr[pivot - 1]) {
                        return false;
                    }
                    pivot--;
                }
            }
  
            // To check if the elements to the right
            // of the pivot are in ascending or not
            pivot=temp;
            else {
                pivot++;
                while (pivot < r) {
                    if (arr[pivot] > arr[pivot + 1]) {
                        return false;
                    }
                    pivot++;
                }
            }
  
            // If any of the above if or else is true
            // Then the array is sorted rotated
            return true;
        }
  
        // Else the array is not sorted rotated
        else {
            return false;
        }
    }
  
    // Driver code
    public static void Main(String[] args)
    {
        int []arr = { 3, 4, 5, 1, 2 };
        Console.WriteLine(isRotated(arr, 5));
    }
}
 
// This code contributed by Rajput-Ji

Javascript

<script>
 
// Function to return the
// index of the pivot
function findPivot(arr, low, high)
{
    // Base cases
    if (high < low)
        return -1;
    if (high == low)
        return low;
 
    var mid = parseInt((low + high) / 2);
    if (mid < high && arr[mid + 1] < arr[mid])
    {
        return mid;
    }
 
    // Check if element at (mid - 1) is pivot
    // Consider the cases like {4, 5, 1, 2, 3}
    if (mid > low && arr[mid] < arr[mid - 1])
    {
        return mid - 1;
    }
 
    // Decide whether we need to go to
    // the left half or the right half
    if (arr[low] > arr[mid])
    {
        return findPivot(arr, low, mid - 1);
    }
    else
    {
        return findPivot(arr, mid + 1, high);
    }
}
 
// Function to check if a given array
// is sorted rotated or not
function isRotated(arr, n)
{
    var l = 0;
    var r = n - 1;
    var pivot = -1;
    if (arr[l] > arr[r])
    {
        pivot = findPivot(arr, l, r);
        var temp=pivot;
        // To check if the elements to the left
        // of the pivot are in descending or not
        if (l < pivot)
        {
            while (pivot > l)
            {
                if (arr[pivot] < arr[pivot - 1])
                {
                    return false;
                }
                pivot--;
            }
        }
 
        // To check if the elements to the right
        // of the pivot are in ascending or not
         
        else
        {
            pivot=temp;
            pivot++;
            while (pivot < r) {
                if (arr[pivot] > arr[pivot + 1]) {
                    return false;
                }
                pivot++;
            }
        }
 
        // If both of the above if is true
        // Then the array is sorted rotated
        return true;
    }
 
    // Else the array is not sorted rotated
    else {
        return false;
    }
}
 
// Driver code
var arr = [4, 5, 1, 3, 2];
if (isRotated(arr, 5))
    document.write("true");
else
    document.write("false");
 
</script>
Producción: 

true

 

Complejidad temporal: O(N) como: 

  • El elemento pivote se encuentra mediante la búsqueda binaria en O (registro N)
  • Pero para verificar si la parte izquierda o la parte derecha está en orden descendente o ascendente, se necesita tiempo O (N) en el peor de los casos.
  • Por lo tanto, la complejidad temporal total es O(N)

Publicación traducida automáticamente

Artículo escrito por Chandan Singh 4 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 *