Buscando un número en una matriz ordenada rotada

Dada una matriz ordenada que se puede rotar, encuentre un elemento en ella con una complejidad de tiempo mínima.

por ejemplo: los contenidos de la matriz pueden ser [8, 1, 2, 3, 4, 5]. Supongamos que busca 8 en él.

La solución aún funciona en una búsqueda binaria en el sentido de que necesitará dividir la matriz en dos partes para examinarla.

En una matriz ordenada, simplemente observa cada parte y determina si el elemento vive en la primera parte (llamémosla A) o la segunda parte (B). Dado que, por la definición de una matriz ordenada, las particiones A y B se ordenarán, esto no requiere más que algunas comparaciones simples de los límites de partición y su clave de búsqueda.

En una matriz ordenada rotativa, solo se puede garantizar que se clasifique uno de A y B. Si el elemento se encuentra dentro de una parte que está ordenada, entonces la solución es simple: simplemente realice la búsqueda como si estuviera haciendo una búsqueda binaria normal. Sin embargo, si debe buscar una parte no ordenada, simplemente llame de forma recursiva a su función de búsqueda en la parte no ordenada.

Esto termina dando una complejidad de tiempo de O(lg n) .

(De manera realista, creo que una estructura de datos así tendría un índice que la acompañe para indicar cuántas posiciones ha girado la matriz).

Editar : Una búsqueda en Google me lleva a este tema un tanto anticuado (pero correcto) en CodeGuru sobre el mismo problema. Para agregar a mi respuesta, copiaré algún pseudocódigo que haya sido dado allí para que aparezca aquí con mi solución (el pensamiento sigue las mismas líneas):

 Search(set): if size of set is 1 and set[0] == item return info on set[0] divide the set into parts A and B if A is sorted and the item is in the A's range return Search(A) if B is sorted and the item is in the B's range return Search(B) if A is not sorted return Search(A) if B is not sorted return Search(B) return "not found" 

O (log (N))

Reducido al problema de encontrar la posición numérica más grande, que se puede hacer verificando el primer y el último y el número medio del área, reducir recursivamente el área, dividir y conquistar, Esto es O (log (N)) no más grande que el búsqueda binaria O (log (N)).

EDITAR: Por ejemplo, tienes

 6 7 8 1 2 3 4 5 ^ ^ ^ 

Al mirar los 3 números, usted sabe que la ubicación de los números más pequeños / más grandes (se llamará mark más adelante) está en el área de 6 7 8 1 2, por lo que 3 4 5 está fuera de consideración (generalmente se hace moviendo su área índice inicial / final (int) que apunta al número 6 y 2).

Próximo paso,

 6 7 8 1 2 ^ ^ ^ 

Una vez más, obtendrá información suficiente para decir de qué lado (izquierda o derecha) está la marca, luego el área se reducirá a la mitad otra vez (a 6 7 8).

Esta es la idea: creo que se puede refinar una mejor versión de esto, de hecho, para una entrevista, un algoritmo OK con un código limpio es mejor que el mejor algoritmo con códigos OK: es mejor que algunos lo usen calentar.

¡Buena suerte!

Recientemente me preguntaron esta pregunta en una entrevista. La pregunta fue describir un algoritmo para buscar una “clave” en una matriz ordenada circular. También se me pidió que escribiera el código para la misma. Esto es lo que se me ocurrió:

Utilice dividir y conquistar búsqueda binaria. Para cada subcampo, compruebe si la matriz está ordenada. Si está ordenado, use la búsqueda binaria clásica, por ejemplo

data [start]

  public boolean search(int start,int end){ int mid =(start+end)/2; if(start>end) { return false; } if(data[start] 

donde normalBinarySearch es una búsqueda binaria simple.

Es una simple modificación de la búsqueda binaria normal. De hecho, funcionaremos tanto para matrices giradas como ordenadas. En el caso de arreglos ordenados, terminará haciendo más trabajo del que realmente necesita.

Para una matriz girada, cuando se divide la matriz en dos submatrices, es posible que uno de esos subcampos no esté en orden. Puede verificar fácilmente si cada mitad se ordena comparando el primer y el último valor en el subcampo.

Sabiendo si cada subcampo está ordenado o no, podemos hacer una elección de qué hacer a continuación.

1) el subarreglo izquierdo está ordenado, y el valor está dentro del rango del subarreglo izquierdo (¡marque ambos extremos!)

Luego busque de forma recursiva buscar subcampo izquierdo.

2) el subarreglo derecho está ordenado, y el valor está dentro del rango del subcampo derecho (¡comprueba ambos extremos!)

Luego busque recursivamente subarreglo correcto.

3) a la izquierda no está clasificado

Luego busque recursivamente subcampo izquierdo

4) Right is Not sorted

Luego busque recursivamente subarreglo correcto.

Nota: la diferencia entre esto y una búsqueda binaria normal es que no podemos simplemente elegir el subarreglo para que se repita simplemente comparando el último subarreglo de valor izquierdo (del primer valor del subarreglo derecho) para tomar nuestra decisión. El valor debe estar estrictamente en el subarreglo izquierdo o derecho y ese subcampo debe clasificarse; de ​​lo contrario, debemos recurrir en el subarreglo sin clasificar.

Aquí hay algunos Objective-C que implementa esto:

 @implementation BinarySearcher - (BOOL)isValue:(int)value inArray:(int[])array withArraySize:(int)size { return [self subSearchArray:array forValue:value fromIndex:0 toIndex:size -1]; } - (BOOL)subSearchArray:(int[])array forValue:(int)value fromIndex:(int)left toIndex:(int)right { if (left < = right) { int middle = (left + right) / 2; BOOL leftArraySorted = array[left] <= array[middle]; BOOL rightArraySorted = array[middle + 1] <= array[right]; if (array[middle] == value) { return YES; } else if (leftArraySorted && value >= array[left] && value < array[middle]) { return [self subSearchArray:array forValue:value fromIndex:left toIndex:middle]; } else if (rightArraySorted && value >= array[middle + 1] && value < = array[right]) { return [self subSearchArray:array forValue:value fromIndex:middle + 1 toIndex:right]; } else if (!leftArraySorted) { return [self subSearchArray:array forValue:value fromIndex:left toIndex:middle]; } else if (!rightArraySorted) { return [self subSearchArray:array forValue:value fromIndex:middle + 1 toIndex:right]; } } return NO; } @end 

En cualquier índice, una partición será ordenada y otra no ordenada. Si la clave se encuentra dentro de la partición clasificada, busque dentro de la matriz ordenada, sino en la partición no ordenada.

 BS(lo, hi) m = (lo + hi)/2 if(k = a[m]) return m b = 0 if(a[hi] > a[m]) b = 1 if(b) if(k > a[m] && k 

Aquí está mi enfoque al respecto:

 public static int findMin(int[] a, int start, int end){ int mid = (start + end)/2; if(start == mid){ return a[mid+1]; }else if(a[start] > a[mid]){ return findMin(a, start, mid); }else if(a[mid+1] > a[start]){ return findMin(a, mid+1, end); }else{ return a[mid+1]; } } 

Complejidad del tiempo: O (log n)

Puede envolver una matriz con una clase que solo expone

E get (índice int);

y se comportaría como una matriz ordenada regular. Por ejemplo, si tiene 4 5 1 2 3 4, wrapper.get (0) devolverá 1.

Ahora puede reutilizar la solución de búsqueda binaria.

Wrapper puede verse así:

 class RotatedArrayWrapper { int startIndex; private final List rotatedArray; public RotatedArrayWrapper(List rotatedArray) { this.rotatedArray = rotatedArray; //find index of the smalest element in array //keep in mind that there might be duplicates startIndex = ... } public T get(int index) { int size = rotatedArray.size(); if (index > size) throw Exception... int actualIndex = (startIndex + index) % size; return rotatedArray.get(actualIndex); } } 

Implementación de Python Podría ser más pythonico:

 from bisect import bisect_left def index(a, x): """Binary search to locate the leftmost value exactly equal to x. see http://docs.python.org/2/library/bisect.html#searching-sorted-lists >>> index([5, 14, 27, 40, 51, 70], 27) 2 >>> index([1, 2, 3, 4], 10) Traceback (most recent call last): ... ValueError """ i = bisect_left(a, x) if i != len(a) and a[i] == x: return i raise ValueError def _index_shifted(value, sequence, start, stop): """Recursive reset location and binary search""" # if at reset (min) and it's not the value, it's not there if start == stop and sequence[start] != value: return -1 mid = (stop + start) // 2 # check mid, since we are already here if sequence[mid] == value: return mid # right side is sorted elif sequence[mid] < sequence[stop]: # if value falls in range, search righ if sequence[stop] >= value > sequence[mid]: return index(sequence[mid:stop + 1], value) + mid # partition left side return _index_shifted(value, sequence, start, mid) # left side is sorted else: # if value falls in range, search left if sequence[mid] > value >= sequence[start]: return index(sequence[start:mid], value) + start # partition right side return _index_shifted(value, sequence, mid + 1, stop) def index_shifted(sequence, value): """Returns index of value in a shifted sorted sequence; -1 if not present. >>> index_shifted([10, 13, 16, 19, 22, 25, 28, 31, 34, 37], 10) 0 >>> index_shifted([10, 13, 16, 19, 22, 25, 28, 31, 34, 37], 37) 9 >>> index_shifted([34, 37, 10, 13, 16, 19, 22, 25, 28, 31], 10) 2 >>> index_shifted([34, 37, 10, 13, 16, 19, 22, 25, 28, 31], 37) 1 >>> index_shifted([34, 37, 10, 13, 16, 19, 22, 25, 28, 31], 13) 3 >>> index_shifted([34, 37, 10, 13, 16, 19, 22, 25, 28, 31], 25) 7 >>> index_shifted([25, 28, 31, 34, 37, 10, 13, 16, 19, 22], 10) 5 >>> index_shifted([25, 28, 31, 34, 37, 10, 13, 16, 19, 22], -10) -1 >>> index_shifted([25, 28, 31, 34, 37, 10, 13, 16, 19, 22], 100) -1 """ return _index_shifted(value, sequence, 0, len(sequence) - 1) 

// esta solución divide la matriz en dos subarreglos iguales utilizando recursión y aplica la búsqueda binaria en una matriz ordenada individual y continúa dividiendo la matriz no ordenada

 public class SearchRotatedSortedArray { public static void main(String... args) { int[] array={5,6,1,2,3,4}; System.out.println(search(array,Integer.parseInt(args[0]),0,5)); } public static boolean search(int[] array,int element,int start,int end) { if(start>=end) { if (array[end]==element) return true;else return false; } int mid=(start+end)/2; if(array[start] 
 int findIndexInRotatedSort( vector input, int s, int e, int toFind ) { if (s > e || s >= input.size() || e < 0) { return -1; } int m = (s + e)/2; int sVal = input.at(s); int eVal = input.at(e); int mVal = input.at(m); if (sVal == toFind) return s; if (eVal == toFind) return e; if (mVal == toFind) return m; bool isFirstOrdered = (sVal < mVal); bool isSecondOrdered = (mVal < eVal); if (toFind > mVal) { if (!isSecondOrdered || toFind < eVal) { return findIndexInRotatedSort( input, m+1, e, toFind ); } else { return findIndexInRotatedSort( input, s, m-1, toFind ); } } else { if (!isFirstOrdered || toFind > sVal) { return findIndexInRotatedSort( input, s, m-1, toFind ); } else { return findIndexInRotatedSort( input, m+1, e, toFind ); } } } 
 public class RoatatedSorted { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub int[] rotArray = {5,6,7,8,9,10,15,16,17,1,2,3,4,}; search(rotArray,0,rotArray.length-1,10); } private static void search(int[] a, int low, int high,int key) { //int mid = low + (high-low)/2; //if(a[mid]==a[key]){System.out.println("element found at" + key+1 +" position"); return;} // find pos to split array int pos = findSplitIndex(a,low,high); System.out.println("split pos found at" + pos +" position"); if(key>=a[low]&& key < =a[pos]) bsearch(a,low,pos,key); if(key>=a[pos+1]&& key < =a[high]) bsearch(a,pos+1,high,key); } private static void bsearch(int[] a, int low, int high,int key) { // TODO Auto-generated method stub if(low>high) return; int mid = low + (high-low)/2; if(a[mid]==key) {System.out.println("element found at" + ++mid +" position"); return;} if(a[mid] > key) bsearch(a,low,mid-1,key); if(a[mid]high)return -1; while(true) { mid = low + (high-low)/2; if( a[mid]>a[mid+1]) break; if(a[mid]>a[low]) low=mid; if(a[high]>a[mid]) high=mid; } return mid; } } 

Primero, para encontrar el elemento Mínimo en la matriz, luego divide la matriz en dos partes. Después de eso busca el valor dado usando el árbol de búsqueda binario. Complejidad: O (logn) Si tiene que encontrar el elemento Mínimo en la Matriz girada, use el mismo enfoque, solo saltee la Búsqueda Binaria. Complejidad: O (logn)

 //Search an element in a sorted and pivoted array class SearchInPivotedSortedArray { //searchInOrtedPivotedArray : Return index of matched element with given value. public static int searchInSortedPivotedArray(int[] A, int value) { int min = findMinElement(A,0,A.Length-1); if (min == A[0]) return binarySearchTree(A, 0, A.Length-1, value); if (value < = A[A.Length-1]) return binarySearchTree(A, min, A.Length-1, value); else return binarySearchTree(A, 0, min-1, value); } //return index of Pivot element public static int findMinElement(int[] Array, int low, int high) { if (low >= high) return low; int mid = (low + high) / 2; if (mid > low && Array[mid] < Array[mid - 1]) return mid; if (mid < high && Array[mid] > Array[mid + 1]) return mid + 1; if (Array[mid] < Array[high]) return findMinElement(Array, low, mid - 1); return findMinElement(Array, mid + 1, high); } //Return match element index, if not found return -1 public static int binarySearchTree(int[] array, int low, int high,int value) { if (low > high) return -1; int mid = (low + high)/2; if (array[mid] == value) return mid; if (array[mid] > value) return binarySearchTree(array, low, mid - 1, value); else return binarySearchTree(array, mid + 1, high, value); } } 

esta es una solución O (logn): probada. funciona en arreglos ordenados y rotados ordenados:

 public static int rbs(int[] a, int l, int r, int t) { if (a[l] < = a[r]) { return bs(a, l, r, t); } if (r < l) { return -1; } else { int m = (l+r) / 2; if (a[m] == t) { return m; } else if (a[m] > t) { // check left half if (a[l] > a[m]) { // left is unsorted return rbs(a, l, m-1, t); } else { // left is sorted if (a[l] < t) { // t is in range return bs(a, l, m-1, t); } else if (a[l] > t) { // t is out of range on left if (a[r] >= t) { return rbs (a, m+1, r, t); } else return -1; } else return l; } } else { // other side if (a[r] < a[m]) { // right is unsorted return rbs(a, m+1, r, t); } else { // right is sorted if (a[r] > t) { // t is in range return bs(a, m+1, r, t); } else if (a[r] < t) { // t is out of range on right side if (a[l] <= t) { return rbs (a, l, m-1, t); } else return -1; } else return r; } } } } public static int bs(int[] a, int l, int r, int t) { int m = (l+r) / 2; if (r < l) { return -1; } else { if (a[m] == t) return m; else if (a[m] < t) return bs(a, m+1, r, t); else return bs (a, l, m-1, t); } } 

Pruebe esta solución,

  public static int findElement(int[] a, int key, int left, int right) { if (left > right) { return -1; } int mid = (left + right) / 2; if (key == a[mid]) { return mid; } else if (key < a[mid]) { return (a[left] <= a[mid] && a[left] < key ? findElement( a, key, left, mid - 1) : findElement(a, key, mid + 1, right)); } else { return (a[mid] <= a[right] && a[right] < key ? findElement( a, key, left, mid - 1) : findElement(a, key, mid + 1, right)); } } 

Aquí hay una implementación en C ++ de la respuesta de @Andrew Song

 int search(int A[], int s, int e, int k) { if (s < = e) { int m = s + (e - s)/2; if (A[m] == k) return m; if (A[m] < A[e] && k > A[m] && k < = A[e]) return search(A, m+1, e, k); if (A[m] > A[s] && k < A[m] && k >= A[s]) return search(A, s, m-1, k); if (A[m] < A[s]) return search(A, s, m-1, k); if (A[m] > A[e]) return search(A, m+1, e, k); } return -1; } 

Esta es una solución 100% funcional y probada en PYTHON

Progtwig para encontrar un número de una matriz ordenada pero rotada

 def findNumber(a, x, start, end): if start > end: return -1 mid = (start + end) / 2 if a[mid] == x: return mid ## Case : 1 if a[start] to a[mid] is sorted , then search first half of array if a[start] < a[mid]: if (x >= a[start] and x < = a[mid]): return findNumber(a, x, start, mid - 1) else: return findNumber(a,x, mid + 1, end) ## Case: 2 if a[start] to a[mid] is not sorted , then a[mid] to a[end] mist be sorted else: if (x >= a[mid] and x < = a[end]): return findNumber(a, x, mid + 1, end) else: return findNumber(a,x, start, mid -1) a = [4,5,6,7,0,1,2] print "Your array is : " , a x = input("Enter any number to find in array : ") result = findNumber(a, x, 0, len(a) - 1) print "The element is present at %d position: ", result 

def search (array, left, right, target): # Condiciones de parada para la recursión. if not array: return -1 if left == right: return left if array [left] == ​​target else -1

  # Check if middle element is same as the target. mid = (left + right) / 2 if array[mid] == target: return mid # Pivot point is at the right of the middle element. if array[left] < = array[mid]: if target >= array[left] and target < = array[mid]: return search(array, left, mid - 1, target) return search(array, mid + 1, right, target) # Pivot point is at the left of the middle element. if target >= array[mid] and target < = array[right]: return search(array, mid + 1, right, target) return search(array, left, mid - 1, target) 

Encontré la solución de esta publicación

Mi solución: eficiencia: O (logn)

 public static int SearchRotatedSortedArray(int l, int d, int[] array, int toFind) { if (l >= d) { return -1; } if (array[l] == toFind) { return l; } if (array[d] == toFind) { return d; } int mid = (l + d) / 2; if (array[mid] == toFind) { return mid; } if ((array[mid] > toFind && toFind > array[l]) || (array[mid] < toFind && array[d] < toFind)) { return SearchRotatedSortedArray(l, mid - 1, array, toFind); } else { return SearchRotatedSortedArray(mid + 1, d, array, toFind); } } 

En el peor de los casos, debe usar la búsqueda lineal y examinar toda la matriz para encontrar un objective, porque, a diferencia de un conjunto, una matriz puede contener duplicados. Y si una matriz contiene duplicados, no puede usar la búsqueda binaria en el problema dado.

Si las consultas en una matriz particular son poco frecuentes, puede utilizar la búsqueda binaria estándar si la matriz completa está ordenada (el primer elemento es estrictamente más pequeño que el último elemento) y utilizar la búsqueda lineal en caso contrario. Para obtener más información, consulte ¿Qué tan rápido puede hacer una búsqueda lineal? discusión sobre StackOverflow y 10 optimizaciones en el artículo de búsqueda lineal de Thomas A. Limoncelli.

Hovewer, si las consultas son frecuentes, puede ordenar la matriz de entrada en tiempo lineal (consulte el algoritmo más rápido para la matriz de N del tamaño de círculo para la discusión de la posición M en StackOverflow) en el paso de preprocesamiento y use la búsqueda binaria estándar como de costumbre.

 #include using namespace std; int BinarySearch(int *a,int key, int length) { int l=0,r=length-1,res=-1; while(l< =r) { int mid = (l+r)/2; if(a[mid] == key) {res = mid; break;} //Check the part of the array that maintains sort sequence and update index // accordingly. if((a[mid] < a[r] && ( key > a[mid] && key < =a[r])) || a[mid] > a[r] && !( key>=a[l] && key  

Buscar índice de elemento en matriz ordenada rotada

 Example : [6,7,8,1,2,3,5] int findElementIndex(int []a, int element, int start, int end) { int mid = (start + end)>>1; if(start>end) return -1; if(a[mid] == element) return mid; if(a[mid] < a[start]) { if(element <= a[end] && element > a[mid]) { return findElementIndex(a,element,mid+1,end); } else{ return findElementIndex(a,element,start,mid-1); } } else if(a[mid] > a[start]){ if(element >= a[start] && element < a[mid]) return findElementIndex(a,element,start,mid-1); else return findElementIndex(a,element,mid+1,end); } else if (a[mid] == a[start]){ if(a[mid] != a[end]) // repeated elements return findElementIndex(a,element,mid+1,end); else int left = findElementIndex(a,element,start,mid-1); int right = findElementIndex(a,element,mid+1,end); return (left != -1) ? left : right; } }