Buscando en una matriz ordenada y rotada

Mientras me preparaba para una entrevista, me topé con esta interesante pregunta:

Se le ha dado una matriz que se ordena y luego se gira.

Por ejemplo:

• Let arr = [1,2,3,4,5], que está ordenado
• Gírelo dos veces hacia la derecha para dar [4,5,1,2,3].

Ahora, ¿cuál es la mejor manera de buscar en esta matriz ordenada + rotada?

Se puede anular la rotación de la matriz y luego hacer una búsqueda binaria. Pero eso no es mejor que hacer una búsqueda lineal en la matriz de entrada, ya que ambos son O (N) en el peor de los casos.

Proporcione algunos consejos. He buscado en Google muchos algoritmos especiales para esto, pero no pude encontrar ninguno.

Entiendo C y C ++.

Esto se puede hacer O(logN)usando una búsqueda binaria ligeramente modificada.

La propiedad interesante de una matriz ordenada + rotada es que cuando la divide en dos mitades, al menos una de las dos mitades siempre estará ordenada.

Let input array arr = [4,5,6,7,8,9,1,2,3]
number of elements  = 9
mid index = (0+8)/2 = 4

[4,5,6,7,8,9,1,2,3]
         ^
 left   mid  right

como parece, la submatriz derecha no está ordenada mientras que la submatriz izquierda está ordenada.

Si mid es el punto de rotación, se ordenarán las submatrices izquierda y derecha.

[6,7,8,9,1,2,3,4,5]
         ^

Pero en cualquier caso se debe ordenar una mitad (submatriz) .

Podemos saber fácilmente qué mitad está ordenada comparando el elemento inicial y final de cada mitad.

Una vez que encontremos qué mitad está ordenada, podemos ver si la clave está presente en esa comparación medio simple con los extremos.

Si la clave está presente en esa mitad, llamamos recursivamente a la función en esa mitad; de lo
contrario, llamamos recursivamente a nuestra búsqueda en la otra mitad.

Descartamos la mitad de la matriz en cada llamada que hace este algoritmo O(logN).

Pseudo código:

function search( arr[], key, low, high)

        mid = (low + high) / 2

        // key not present
        if(low > high)
                return -1

        // key found
        if(arr[mid] == key)
                return mid

        // if left half is sorted.
        if(arr[low] <= arr[mid])

                // if key is present in left half.
                if (arr[low] <= key && arr[mid] >= key) 
                        return search(arr,key,low,mid-1)

                // if key is not present in left half..search right half.
                else                 
                        return search(arr,key,mid+1,high)
                end-if

        // if right half is sorted. 
        else    
                // if key is present in right half.
                if(arr[mid] <= key && arr[high] >= key) 
                        return search(arr,key,mid+1,high)

                // if key is not present in right half..search in left half.
                else
                        return search(arr,key,low,mid-1)
                end-if
        end-if  

end-function

La clave aquí es que siempre se ordenará una submatriz, con lo cual podemos descartar la mitad de la matriz.

La respuesta aceptada tiene un error cuando hay elementos duplicados en la matriz. Por ejemplo, arr = {2,3,2,2,2}y 3 es lo que estamos buscando. Entonces, el programa en la respuesta aceptada devolverá -1 en lugar de 1.

Esta pregunta de la entrevista se analiza en detalle en el libro "Cracking the Coding Interview". La condición de los elementos duplicados se analiza especialmente en ese libro. Dado que la operación dijo en un comentario que los elementos de la matriz pueden ser cualquier cosa, estoy dando mi solución como pseudo código a continuación:

function search( arr[], key, low, high)

    if(low > high)
        return -1

    mid = (low + high) / 2

    if(arr[mid] == key)
        return mid

    // if the left half is sorted.
    if(arr[low] < arr[mid]) {

        // if key is in the left half
        if (arr[low] <= key && key <= arr[mid]) 
            // search the left half
            return search(arr,key,low,mid-1)
        else
            // search the right half                 
            return search(arr,key,mid+1,high)
        end-if

    // if the right half is sorted. 
    else if(arr[mid] < arr[low])    
        // if the key is in the right half.
        if(arr[mid] <= key && arr[high] >= key) 
            return search(arr,key,mid+1,high)
        else
            return search(arr,key,low,mid-1)
        end-if

    else if(arr[mid] == arr[low])

        if(arr[mid] != arr[high])
            // Then elements in left half must be identical. 
            // Because if not, then it's impossible to have either arr[mid] < arr[high] or arr[mid] > arr[high]
            // Then we only need to search the right half.
            return search(arr, mid+1, high, key)
        else 
            // arr[low] = arr[mid] = arr[high], we have to search both halves.
            result = search(arr, low, mid-1, key)
            if(result == -1)
                return search(arr, mid+1, high, key)
            else
                return result
   end-if
end-function

Puede hacer 2 búsquedas binarias: primero para encontrar el índice ital que arr[i] > arr[i+1].

Aparentemente, (arr\[1], arr[2], ..., arr[i])y (arr[i+1], arr[i+2], ..., arr[n])ambos son matrices ordenadas.

Entonces arr[1] <= x <= arr[i], si haces una búsqueda binaria en la primera matriz, de lo contrario en la segunda.

La complejidad O(logN)

EDITAR: el código .

Mi primer intento sería encontrar usando la búsqueda binaria el número de rotaciones aplicadas - esto se puede hacer encontrando el índice n donde a [n]> a [n + 1] usando el mecanismo de búsqueda binaria habitual. Luego, haga una búsqueda binaria regular mientras rota todos los índices por turno encontrado.

int rotated_binary_search(int A[], int N, int key) {
  int L = 0;
  int R = N - 1;

  while (L <= R) {
    // Avoid overflow, same as M=(L+R)/2
    int M = L + ((R - L) / 2);
    if (A[M] == key) return M;

    // the bottom half is sorted
    if (A[L] <= A[M]) {
      if (A[L] <= key && key < A[M])
        R = M - 1;
      else
        L = M + 1;
    }
    // the upper half is sorted
    else {
      if (A[M] < key && key <= A[R])
        L = M + 1;
      else
        R = M - 1;
    }
  }
  return -1;
}

Si sabe que la matriz se ha girado s hacia la derecha, simplemente puede hacer una búsqueda binaria desplazada s hacia la derecha. Esto es O (lg N)

Con esto, quiero decir, inicialice el límite izquierdo as y el derecho a (s-1) mod N, y haga una búsqueda binaria entre estos, teniendo un poco de cuidado para trabajar en el área correcta.

Si no sabe cuánto se ha girado la matriz, puede determinar qué tan grande es la rotación usando una búsqueda binaria, que es O (lg N), luego haga una búsqueda binaria con desplazamiento, O (lg N), a gran total de O (lg N) todavía.

Si sabe qué tan (lejos) se giró, aún puede hacer una búsqueda binaria.

El truco es que obtienes dos niveles de índices: haces los bs en un rango virtual 0..n-1 y luego los des-rota cuando buscas un valor.

Respuesta a la publicación mencionada anteriormente "Esta pregunta de la entrevista se analiza en detalle en el libro 'Cracking the Coding Interview'. La condición de los elementos duplicados se analiza especialmente en ese libro. Dado que la operación dijo en el comentario que los elementos de la matriz pueden ser cualquier cosa, estoy dando mi solución como pseudo código a continuación: "

Tu solución es O (n) !! (La última condición if donde verifica ambas mitades de la matriz para una sola condición lo convierte en un sol de complejidad de tiempo lineal)

Es mejor hacer una búsqueda lineal que quedarme atrapado en un laberinto de errores y fallas de segmentación durante una ronda de codificación.

No creo que haya una mejor solución que O (n) para una búsqueda en una matriz ordenada rotada (con duplicados)

No es necesario rotar la matriz primero. Puede utilizar la búsqueda binaria en la matriz rotada (con algunas modificaciones).

Sea N el número que está buscando:

Lea el primer número (arr [inicio]) y el número en el medio de la matriz (arr [final]):

• if arr [inicio]> arr [final] -> la primera mitad no está ordenada pero la segunda mitad está ordenada:

  • si arr [fin]> N -> el número está en el índice: (medio + N - arr [fin])

  • si N repita la búsqueda en la primera parte de la matriz (vea que el final es el medio de la primera mitad de la matriz, etc.)

(lo mismo si la primera parte está ordenada pero la segunda no)

public class PivotedArray {

//56784321 first increasing than decreasing
public static void main(String[] args) {
    // TODO Auto-generated method stub
    int [] data ={5,6,7,8,4,3,2,1,0,-1,-2};

    System.out.println(findNumber(data, 0, data.length-1,-2));

}

static int findNumber(int data[], int start, int end,int numberToFind){

    if(data[start] == numberToFind){
        return start;
    }

    if(data[end] == numberToFind){
        return end;
    }
    int mid = (start+end)/2;
    if(data[mid] == numberToFind){
        return mid;
    }
    int idx = -1;
    int midData = data[mid];
    if(numberToFind < midData){
        if(midData > data[mid+1]){
            idx=findNumber(data, mid+1, end, numberToFind);
        }else{
            idx =  findNumber(data, start, mid-1, numberToFind);
        }
    }

    if(numberToFind > midData){
        if(midData > data[mid+1]){
            idx =  findNumber(data, start, mid-1, numberToFind);

        }else{
            idx=findNumber(data, mid+1, end, numberToFind);
        }
    }
    return idx;
}

}

short mod_binary_search( int m, int *arr, short start, short end)
{

 if(start <= end)
 {
    short mid = (start+end)/2;

    if( m == arr[mid])
        return mid;
    else
    {
        //First half is sorted
        if(arr[start] <= arr[mid])
        {
            if(m < arr[mid] && m >= arr[start])
                return mod_binary_search( m, arr, start, mid-1);
            return mod_binary_search( m, arr, mid+1, end);
        }

        //Second half is sorted
        else
        {
            if(m > arr[mid] && m < arr[start])
                return mod_binary_search( m, arr, mid+1, end);
            return mod_binary_search( m, arr, start, mid-1);
        }
    }
 }
 return -1;
}

Primero, necesita encontrar la constante de desplazamiento, k. Esto se puede hacer en tiempo O (lgN). A partir del cambio constante k, puede encontrar fácilmente el elemento que está buscando mediante una búsqueda binaria con la constante k. La búsqueda binaria aumentada también toma tiempo O (lgN) El tiempo de ejecución total es O (lgN + lgN) = O (lgN)

Para encontrar el desplazamiento constante, k. Solo tienes que buscar el valor mínimo en la matriz. El índice del valor mínimo de la matriz le indica el cambio constante. Considere la matriz ordenada [1,2,3,4,5].

Los posibles cambios son:
    [1,2,3,4,5] // k = 0
    [5,1,2,3,4] // k = 1
    [4,5,1,2,3] // k = 2
    [3,4,5,1,2] // k = 3
    [2,3,4,5,1] // k = 4
    [1,2,3,4,5] // k = 5% 5 = 0 

Para hacer cualquier algoritmo en tiempo O (lgN), la clave es encontrar siempre formas de dividir el problema por la mitad. Una vez hecho esto, el resto de los detalles de implementación es fácil

A continuación se muestra el código en C ++ para el algoritmo

// This implementation takes O(logN) time
// This function returns the amount of shift of the sorted array, which is
// equivalent to the index of the minimum element of the shifted sorted array. 
#include <vector> 
#include <iostream> 
using namespace std; 

int binarySearchFindK(vector<int>& nums, int begin, int end)
{
    int mid = ((end + begin)/2); 
    // Base cases
    if((mid > begin && nums[mid] < nums[mid-1]) || (mid == begin && nums[mid] <= nums[end]))     
        return mid; 
    // General case 
    if (nums[mid] > nums[end]) 
    {
        begin = mid+1; 
        return binarySearchFindK(nums, begin, end); 
    }
    else
    {
        end = mid -1; 
        return binarySearchFindK(nums, begin, end); 
    }   
}  
int getPivot(vector<int>& nums)
{
    if( nums.size() == 0) return -1; 
    int result = binarySearchFindK(nums, 0, nums.size()-1); 
    return result; 
}

// Once you execute the above, you will know the shift k, 
// you can easily search for the element you need implementing the bottom 

int binarySearchSearch(vector<int>& nums, int begin, int end, int target, int pivot)
{
    if (begin > end) return -1; 
    int mid = (begin+end)/2;
    int n = nums.size();  
    if (n <= 0) return -1; 

    while(begin <= end)
    {
        mid = (begin+end)/2; 
        int midFix = (mid+pivot) % n; 
        if(nums[midFix] == target) 
        {
            return midFix; 
        }
        else if (nums[midFix] < target)
        {
            begin = mid+1; 
        }
        else
        {
            end = mid - 1; 
        }
    }
    return -1; 
}
int search(vector<int>& nums, int target) {
    int pivot = getPivot(nums); 
    int begin = 0; 
    int end = nums.size() - 1; 
    int result = binarySearchSearch(nums, begin, end, target, pivot); 
    return result; 
}

¡Espero que esto ayude! =)
Pronto Chee Loong, 
Universidad de Toronto 

Para una matriz rotada con duplicados, si se necesita encontrar la primera aparición de un elemento, se puede utilizar el siguiente procedimiento (código Java):

public int mBinarySearch(int[] array, int low, int high, int key)
{
    if (low > high)
        return -1; //key not present

    int mid = (low + high)/2;

    if (array[mid] == key)
        if (mid > 0 && array[mid-1] != key)
            return mid;

    if (array[low] <= array[mid]) //left half is sorted
    {
        if (array[low] <= key && array[mid] >= key)
            return mBinarySearch(array, low, mid-1, key);
        else //search right half
            return mBinarySearch(array, mid+1, high, key);
    }
    else //right half is sorted
    {
        if (array[mid] <= key && array[high] >= key)
            return mBinarySearch(array, mid+1, high, key);
        else
            return mBinarySearch(array, low, mid-1, key);
    }       

}

Esta es una mejora del procedimiento de codaddict anterior. Observe la condición adicional if como se muestra a continuación:

if (mid > 0 && array[mid-1] != key)

Aquí hay una solución de python O (log n) simple (tiempo, espacio) eficiente no recursiva que no modifica la matriz original. Corta la matriz rotada por la mitad hasta que solo tenga dos índices para verificar y devuelve la respuesta correcta si un índice coincide.

def findInRotatedArray(array, num):

lo,hi = 0, len(array)-1
ix = None


while True:


    if hi - lo <= 1:#Im down to two indices to check by now
        if (array[hi] == num):  ix = hi
        elif (array[lo] == num): ix = lo
        else: ix = None
        break

    mid = lo + (hi - lo)/2
    print lo, mid, hi

    #If top half is sorted and number is in between
    if array[hi] >= array[mid] and num >= array[mid] and num <= array[hi]:
        lo = mid

    #If bottom half is sorted and number is in between
    elif array[mid] >= array[lo] and num >= array[lo] and num <= array[mid]:
        hi = mid


    #If top half is rotated I know I need to keep cutting the array down
    elif array[hi] <= array[mid]:
        lo = mid

    #If bottom half is rotated I know I need to keep cutting down
    elif array[mid] <= array[lo]:
        hi = mid

print "Index", ix

Prueba esta solución

bool search(int *a, int length, int key)
{
int pivot( length / 2 ), lewy(0), prawy(length);
if (key > a[length - 1] || key < a[0]) return false;
while (lewy <= prawy){
    if (key == a[pivot]) return true;
    if (key > a[pivot]){
        lewy = pivot;
        pivot += (prawy - lewy) / 2 ? (prawy - lewy) / 2:1;}
    else{
        prawy = pivot;
        pivot -= (prawy - lewy) / 2 ? (prawy - lewy) / 2:1;}}
return false;
}

Este código en C ++ debería funcionar para todos los casos, aunque funciona con duplicados, avíseme si hay un error en este código.

#include "bits/stdc++.h"
using namespace std;
int searchOnRotated(vector<int> &arr, int low, int high, int k) {

    if(low > high)
        return -1;

    if(arr[low] <= arr[high]) {

        int p = lower_bound(arr.begin()+low, arr.begin()+high, k) - arr.begin();
        if(p == (low-high)+1)
            return -1;
        else
            return p; 
    }

    int mid = (low+high)/2;

    if(arr[low] <= arr[mid]) {

        if(k <= arr[mid] && k >= arr[low])
            return searchOnRotated(arr, low, mid, k);
        else
            return searchOnRotated(arr, mid+1, high, k);
    }
    else {

        if(k <= arr[high] && k >= arr[mid+1])
            return searchOnRotated(arr, mid+1, high, k);
        else
            return searchOnRotated(arr, low, mid, k);
    }
}
int main() {

    int n, k; cin >> n >> k;
    vector<int> arr(n);
    for(int i=0; i<n; i++) cin >> arr[i];
    int p = searchOnRotated(arr, 0, n-1, k);
    cout<<p<<"\n";
    return 0;
}

En Javascript

var search = function(nums, target,low,high) {
    low= (low || low === 0) ? low : 0;

    high= (high || high == 0) ? high : nums.length -1;

    if(low > high)
        return -1;

    let mid = Math.ceil((low + high) / 2);


    if(nums[mid] == target)
        return mid;

    if(nums[low] < nums[mid]) {
        // if key is in the left half
        if (nums[low] <= target && target <= nums[mid]) 
            // search the left half
            return search(nums,target,low,mid-1);
        else
            // search the right half                 
            return search(nums,target,mid+1,high);
    } else {
        // if the key is in the right half.
        if(nums[mid] <= target && nums[high] >= target) 
            return search(nums,target,mid+1,high)
        else
            return search(nums,target,low,mid-1)
    }
};

Entrada: nums = [4,5,6,7,0,1,2], objetivo = 0 Salida: 4

import java.util.*;

class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int arr[]=new int[n];
        int max=Integer.MIN_VALUE;
        int min=Integer.MAX_VALUE;
        int min_index=0,max_index=n;

        for(int i=0;i<n;i++){
            arr[i]=sc.nextInt();
            if(arr[i]>max){
                max=arr[i];
            max_index=i;
            }
            if(arr[i]<min){
                min=arr[i];
                min_index=i;
            }

        }

        int element=sc.nextInt();
        int index;
        if(element>arr[n-1]){
            index=Arrays.binarySearch(arr,0,max_index+1,element);
        }
        else {
             index=Arrays.binarySearch(arr,min_index,n,element);
        }
        if(index>=0){
            System.out.println(index);
        }
        else{
            System.out.println(-1);
        }
    }

}

Aquí están mis dos centavos:

• Si la matriz no contiene duplicados, se puede encontrar la solución en O (log (n)). Como muchas personas lo han demostrado, se puede utilizar una versión modificada de la búsqueda binaria para encontrar el elemento de destino.

• Sin embargo, si la matriz contiene duplicados, creo que no hay forma de encontrar el elemento de destino en O (log (n)). Aquí hay un ejemplo que muestra por qué creo que O (log (n)) no es posible. Considere las dos matrices a continuación:

a = [2,.....................2...........3,6,2......2]
b = [2.........3,6,2........2......................2]

Todos los puntos se rellenan con el número 2. Puede ver que ambas matrices están ordenadas y giradas. Si uno quiere considerar la búsqueda binaria, entonces tiene que cortar el dominio de búsqueda a la mitad en cada iteración; así es como obtenemos O (log (n)). Supongamos que estamos buscando el número 3. En el primer caso, podemos verlo escondido en el lado derecho del arreglo, y en el segundo caso se esconde en el segundo lado del arreglo. Esto es lo que sabemos sobre la matriz en esta etapa:

• izquierda = 0
• derecha = longitud - 1;
• medio = izquierda + (derecha - izquierda) / 2;
• arr [mid] = 2;
• arr [izquierda] = 2;
• arr [derecha] = 2;
• objetivo = 3;

Esta es toda la información que tenemos. Podemos ver claramente que no es suficiente tomar la decisión de excluir la mitad de la matriz. Como resultado de eso, la única forma es hacer una búsqueda lineal. No estoy diciendo que no podamos optimizar ese tiempo O (n), todo lo que estoy diciendo es que no podemos hacer O (log (n)).

Hay algo que no me gusta de la búsqueda binaria debido a mid, mid-1, etc., es por eso que siempre uso la búsqueda binary stride / jump

¿Cómo usarlo en una matriz rotada? use dos veces (una vez busque shift y luego use un .at () para encontrar el índice desplazado -> índice original)

O compare el primer elemento, si es menor que el primer elemento, tiene que estar cerca del final

hacer una búsqueda de salto hacia atrás desde el final, detenerse si se encuentra algún pivote

si es> elemento de inicio, simplemente haga una búsqueda de salto normal :)

Implementado usando C #

public class Solution {
        public int Search(int[] nums, int target) {
             if (nums.Length == 0) return -1;
                int low = 0;
                int high = nums.Length - 1;
                while (low <= high)
                {
                    int mid = (low + high) / 2;
                    if (nums[mid] == target) return mid;
                    if (nums[low] <= nums[mid]) // 3 4 5 6 0 1 2
                    {
                        if (target >= nums[low] && target <= nums[mid])
                            high = mid;
                        else
                            low = mid + 1;
                    }
                    else // 5 6 0 1 2 3 4
                    {
                        if (target >= nums[mid] && target <= nums[high])
                            low= mid;
                        else
                            high = mid - 1;
                    }
                }
                return -1;
        }
    }

Otro enfoque que funcionaría con valores repetidos es encontrar la rotación y luego hacer una búsqueda binaria regular aplicando la rotación cada vez que accedemos a la matriz.

test = [3, 4, 5, 1, 2]
test1 = [2, 3, 2, 2, 2]

def find_rotated(col, num):
    pivot = find_pivot(col)
    return bin_search(col, 0, len(col), pivot, num)

def find_pivot(col):
    prev = col[-1]
    for n, curr in enumerate(col):
        if prev > curr:
            return n
        prev = curr
    raise Exception("Col does not seem like rotated array")

def rotate_index(col, pivot, position):
    return (pivot + position) % len(col)

def bin_search(col, low, high, pivot, num):
    if low > high:
        return None
    mid = (low + high) / 2
    rotated_mid = rotate_index(col, pivot, mid)
    val = col[rotated_mid]
    if (val == num):
        return rotated_mid
    elif (num > val):
        return bin_search(col, mid + 1, high, pivot, num)
    else:
        return bin_search(col, low, mid - 1,  pivot, num)

print(find_rotated(test, 2))
print(find_rotated(test, 4))
print(find_rotated(test1, 3))

Mi código simple: -

public int search(int[] nums, int target) {
    int l = 0;
    int r = nums.length-1;
    while(l<=r){
        int mid = (l+r)>>1;
        if(nums[mid]==target){
            return mid;
        }
        if(nums[mid]> nums[r]){
            if(target > nums[mid] || nums[r]>= target)l = mid+1;
            else r = mid-1;
        }
        else{
            if(target <= nums[r] && target > nums[mid]) l = mid+1;
            else r = mid -1;
        }
    }
    return -1;
}

Complejidad de tiempo O (log (N)).

Pregunta: Buscar en matriz ordenada girada

public class SearchingInARotatedSortedARRAY {
    public static void main(String[] args) {
        int[] a = { 4, 5, 6, 0, 1, 2, 3 };

        System.out.println(search1(a, 6));

    }

    private static int search1(int[] a, int target) {
        int start = 0;
        int last = a.length - 1;
        while (start + 1 < last) {
            int mid = start + (last - start) / 2;

            if (a[mid] == target)
                return mid;
            // if(a[start] < a[mid]) => Then this part of the array is not rotated
            if (a[start] < a[mid]) {
                if (a[start] <= target && target <= a[mid]) {
                    last = mid;
                } else {
                    start = mid;
                }
            }
            // this part of the array is rotated
            else {
                if (a[mid] <= target && target <= a[last]) {
                    start = mid;
                } else {
                    last = mid;
                }
            }
        } // while
        if (a[start] == target) {
            return start;
        }
        if (a[last] == target) {
            return last;
        }
        return -1;
    }
}