data structures - data - Buscando un número en una matriz ordenada rotada
data structures types (21)
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.
// 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]<array[end])
{
return binarySearch(array,element,start,end);
}
return search(array,element,start,mid)||search(array,element,mid+1,end);
}
public static boolean binarySearch(int[] array,int element,int start,int end)
{
int mid;
while(start<=end)
{
mid=(start+end)/2;
if(array[mid]==element)
return true;
if(array[mid]<element)
{
start=mid+1;
}
else
{
end=mid-1;
}
}
return false;
}
}
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)
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;
}
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;
}
}
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<a[hi])
BS(m+1, hi)
else
BS(lo, m-1)
En el peor de los casos, debe usar la búsqueda lineal y examinar toda la matriz para encontrar un objetivo, 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 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 ) en el paso de preprocesamiento y use la búsqueda binaria estándar como de costumbre.
Implementación de Python Podría ser más pitónico:
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)
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 this 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"
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);
}
}
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!
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);
}
}
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));
}
}
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<T> {
int startIndex;
private final List<T> rotatedArray;
public RotatedArrayWrapper(List<T> 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);
}
}
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] <data [end] implica que los datos están ordenados. usuario binario más divide la matriz aún más hasta que obtengamos la matriz ordenada.
public boolean search(int start,int end){
int mid =(start+end)/2;
if(start>end)
{
return false;
}
if(data[start]<data[end]){
return this.normalBinarySearch(start, end);
}
else{
//the other part is unsorted.
return (this.search(start,mid) ||
this.search(mid+1,end));
}
}
donde normalBinarySearch es una búsqueda binaria simple.
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
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);
}
}
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
Esta es una solución 100% funcional y probada en PYTHON
Programa 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
#include<iostream>
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 <a[mid]))
{
l = mid+1;
}
else r = mid-1;
}
return res;
}
void main()
{
int arr[10] = {6,7,8,9,10,13,15,18,2,3};
int key = 8;
cout<<"Binary Search Output: "<<BinarySearch(arr,key,10);
}
int findIndexInRotatedSort( vector<int> 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]<key)
bsearch(a,mid+1,high,key);
}
private static int findSplitIndex(int[] a, int low, int high) {
// TODO Auto-generated method stub
int mid;
if(low>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;
}
}