Buscando en una matriz ordenada y rotada

Mientras me preparaba para la entrevista técnica, me encontré con esta interesante pregunta:

Te han dado una matriz que se ordena y luego gira.

ejemplo

Deje arr = [1,2,3,4,5] que se clasifica y luego se gira, diga dos veces a la derecha para dar

[4,5,1,2,3]

Ahora, ¿qué mejor puede uno buscar en esta matriz ordenada + girada?

Uno puede deshacer la matriz y luego hacer una búsqueda binaria. Pero no es mejor que hacer una búsqueda lineal en la matriz de entrada ya que ambas son el peor caso O (N).

Por favor, brinde algunos consejos. He buscado mucho en algoritmos especiales para esto, pero no he podido encontrar ninguno.

Entiendo c y c ++

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

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

 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 correcto, la sub-matriz no está ordenada mientras que la sub-matriz izquierda está ordenada.

Si el medio es el punto de rotación, se ordenarán las sub-matrices izquierda y derecha.

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

Pero en cualquier caso, una mitad (sub-matriz) debe ser ordenada .

Podemos saber fácilmente qué mitad se ordena comparando los elementos de inicio y fin 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, recursivamente llamamos a nuestra búsqueda en la otra mitad.

Estamos descartando la mitad de la matriz en cada llamada que hace que este algoritmo sea 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 una sub-matriz siempre será ordenada, con lo que podemos descartar la mitad de la matriz.

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

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

Entonces, si arr[1] <= x <= arr[i] , se realiza una búsqueda binaria en la primera matriz, en otro caso en la segunda.

La complejidad O(logN)

EDITAR: el código .

La respuesta seleccionada 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. Luego, el progtwig en la respuesta seleccionada devolverá -1 en lugar de 1.

Esta pregunta de la entrevista se trata en detalle en el libro “Cracking the Coding Interview”. La condición de los elementos duplicados se discute especialmente en ese libro. Como la OP 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 

Mi primer bash sería encontrar usando la búsqueda binaria el número de rotaciones aplicadas; esto se puede hacer buscando el índice n donde a [n]> a [n + 1] usa el mecanismo de búsqueda binario habitual. Luego haga una búsqueda binaria regular mientras gira todos los índices por turno encontrado.

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

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

Si no sabe por cuánto ha girado la matriz, puede determinar qué tan grande es la rotación utilizando una búsqueda binaria, que es O (lg N), luego realice una búsqueda binaria desplazada, O (lg N), una gran total de O (lg N) aún.

Si sabe cómo (hasta ahora) 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 giras al buscar un valor.

no es necesario rotar la matriz primero, puede usar la búsqueda binaria en la matriz girada (con algunas modificaciones)

supongamos que N es el número que busca:

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

  • si arr [inicio]> arr [fin] -> la primera mitad no está ordenada, pero la segunda mitad está ordenada:

    • if arr [end]> N -> el número está en índice: (middle + N – arr [end])

    • si N repite la búsqueda en la primera parte de la matriz (vea el extremo para estar en el medio de la primera mitad de la matriz, etc.)

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

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

Respuesta para la publicación mencionada anteriormente “Esta pregunta de la entrevista se trata en detalle en el libro ‘Cracking the Coding Interview’. La condición de los elementos duplicados se discute especialmente en ese libro. Como la OP dijo en comentarios que los elementos de la matriz pueden ser cualquier cosa, estoy dando mi solución como pseudo código en la siguiente página:

Tu solución es O (n) !! (La última condición if donde se verifican 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 quedar atrapado en un laberinto de errores y fallas de segmentación durante una ronda de encoding.

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

 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, necesitas encontrar la constante de cambio, k. Esto se puede hacer en el tiempo O (lgN). A partir del cambio constante k, puede encontrar fácilmente el elemento que está buscando utilizando una búsqueda binaria con la constante k. La búsqueda binaria aumentada también toma el tiempo O (lgN). El tiempo total de ejecución es O (lgN + lgN) = O (lgN)

Para encontrar el cambio 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 a la mitad. Una vez hecho esto, el rest 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  #include  using namespace std; int binarySearchFindK(vector& 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& 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& 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& 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 

Aquí hay una solución simple (tiempo, espacio) eficiente no recursiva de O (log n) python 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 coincide un índice.

 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 

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

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

Para una matriz girada con duplicados, si uno necesita encontrar la primera aparición de un elemento, puede usar 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); } } 

Esto es una mejora al procedimiento de coadicto de arriba. Observe la condición adicional de la siguiente manera:

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

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

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

 #include "bits/stdc++.h" using namespace std; int searchOnRotated(vector &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 arr(n); for(int i=0; i> arr[i]; int p = searchOnRotated(arr, 0, n-1, k); cout<