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