Ricerca di un numero in una matrice ordinata ruotata

Data una matrice ordinata che può essere ruotata, trova un elemento in essa nella complessità temporale minima.

es .: i contenuti dell’array possono essere [8, 1, 2, 3, 4, 5]. Supponi di cercare 8 in esso.

La soluzione funziona ancora con una ricerca binaria, nel senso che sarà necessario suddividere l’array in due parti da esaminare.

In una matrice ordinata, basta osservare ciascuna parte e determinare se l’elemento risiede nella prima parte (chiamiamola A) o nella seconda parte (B). Dato che, con la definizione di un array ordinato, le partizioni A e B verranno ordinate, questo non richiede più di semplici confronti tra i limiti della partizione e la chiave di ricerca.

In un array ordinato ruotato, è ansible garantire che solo uno di A e B sia ordinato. Se l’elemento si trova all’interno di una parte ordinata, la soluzione è semplice: basta eseguire la ricerca come se si stesse eseguendo una normale ricerca binaria. Se, tuttavia, è necessario cercare una parte non ordinata, chiamare semplicemente ricorsivamente la funzione di ricerca nella parte non ordinata.

Questo finisce per dare una complessità temporale di O(lg n) .

(Realisticamente, penserei che una tale struttura di dati avrebbe un indice che lo accompagna per indicare quante posizioni è stata ruotata la matrice).

Modifica : una ricerca su Google mi porta a questo argomento un po ‘datato (ma corretto) su CodeGuru che discute lo stesso problema. Per aggiungere alla mia risposta, copierò qualche pseudocodice che è stato dato lì in modo che appaia qui con la mia soluzione (il pensiero segue le stesse linee):

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

Ridotto al problema di trovare la posizione numero più grande, che può essere fatta controllando il primo e l’ultimo numero medio dell’area, ridurre ricorsivamente l’area, dividere e conquistare, Questo è O (log (N)) non più grande del ricerca binaria O (log (N)).

EDIT: Ad esempio, hai

 6 7 8 1 2 3 4 5 ^ ^ ^ 

Osservando i 3 numeri che conosci, la posizione dei numeri più piccoli / più grandi (sarà chiamata mark in seguito) si trova nell’area di 6 7 8 1 2, quindi 3 4 5 è fuori considerazione (in genere spostando la tua area indice di inizio / fine (int) che punta al numero 6 e 2).

Passo successivo,

 6 7 8 1 2 ^ ^ ^ 

Ancora una volta otterrete informazioni sufficienti per sapere da quale parte (a destra o sinistra) si trova il segno, quindi l’area viene ridotta nuovamente a metà (a 6 7 8).

Questa è l’idea: penso che tu possa perfezionare una versione migliore di questo, in realtà, per un colloquio, un algoritmo OK con un pezzo di codice pulito è migliore del migliore algoritmo con i codici OK: ti sarà meglio farlo da alcuni a riscaldare.

In bocca al lupo!

Mi è stata posta questa domanda in un’intervista di recente. La domanda era descrivere un algoritmo per cercare una “chiave” in un array ordinato circolare. Mi è stato anche chiesto di scrivere il codice per lo stesso. Questo è quello che mi è venuto in mente:

Usa divide e conquista la ricerca binaria. Per ogni sottoarray controlla se l’array è ordinato. Se ordinato, usa la classica ricerca binaria es

data [start]

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

dove normalBinarySearch è una semplice ricerca binaria.

È una semplice modifica della normale ricerca binaria. In effetti, funzionerà sia per gli array ruotati che per quelli ordinati. Nel caso di array ordinati, finirà per fare più lavoro di quanto non sia realmente necessario.

Per un array ruotato, quando si divide l’array in due subarray, è ansible che uno di questi subarray non sia in ordine. È ansible controllare facilmente se ciascuna metà è ordinata confrontando il primo e l’ultimo valore nel sottoarray.

Sapendo se ogni subarray è ordinato o meno, possiamo fare una scelta su cosa fare dopo.

1) left subarray è ordinato, e il valore è compreso nell’intervallo del subarray sinistro (controlla entrambe le estremità!)

Quindi cerca ricorsivamente a sinistra sottoarray.

2) viene ordinato il subarray destro e il valore è compreso nell’intervallo del sottoarray di destra (controllare entrambe le estremità!)

Quindi cerca ricorsivamente a destra sottoarray.

3) a sinistra non è ordinato

Quindi cerca ricorsivamente il sottoarray sinistro

4) Right is Not Sorted

Quindi cerca ricorsivamente a destra sottoarray.

Nota: la differenza tra questa e una normale ricerca binaria è che non possiamo semplicemente scegliere il sottoarray da ricorrere semplicemente confrontando l’ultimo valore del sottoarray sinistro (del primo valore del sottoarray di destra) per prendere la nostra decisione. Il valore deve essere rigorosamente nel subarray sinistro o destro e il sottoarray deve essere ordinato, altrimenti è necessario ricorrere al sottarray non ordinato.

Ecco alcuni Objective-C che implementa questo:

 @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 

A qualsiasi indice, una partizione verrà ordinata e altre non ordinate. Se la chiave si trova all’interno della partizione ordinata, cerca all’interno dell’array ordinato, altrimenti nella partizione non ordinata.

 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 

Ecco il mio approccio a questo:

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

Complessità del tempo: O (log n)

Puoi racchiudere un array con una class che espone solo

E get (indice int);

e si comporterebbe come ordinata matrice ordinata. Ad esempio, se hai 4 5 1 2 3 4, wrapper.get (0) restituirà 1.

Ora puoi solo riutilizzare la soluzione di ricerca binaria.

Wrapper può assomigliare a questo:

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

Implementazione Python. Potrebbe essere più piritico:

 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) 

// questa soluzione divide l’array in due sottoarray uguali usando la ricorsione e applica la ricerca binaria su singoli array ordinati e continua a dividere l’array non ordinato

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

Prima di trovare l’elemento Minimo nell’array, dividere l’array in due parti. Dopo quella ricerca, il valore indicato viene utilizzato mediante l’albero di ricerca binario. Complessità: O (logn) Se devi trovare l’elemento Minimo nella matrice ruotata, usa lo stesso approccio, salta semplicemente la ricerca binaria. Complessità: 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); } } 

questa è una soluzione O (logn): testata. funziona su entrambi gli array ordinati e ruotati:

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

Prova questa soluzione,

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

Ecco un’implementazione in C ++ della risposta di @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; } 

Questa è la soluzione funzionante e testata al 100% in PYTHON

Programma per trovare un numero da una matrice ordinata ma ruotata

 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): # Interrompi le condizioni per la ricorsione. se non array: return -1 se lasciato == right: return left se 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) 

Ho trovato la soluzione da questo post

La mia soluzione: efficienza: 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); } } 

Nel peggiore dei casi devi usare la ricerca lineare ed esaminare l’intero array per trovare un bersaglio, perché, diversamente da un set, un array può contenere duplicati. E se un array contiene duplicati non puoi usare la ricerca binaria nel problema dato.

Se le query su determinati array non sono frequenti, è ansible utilizzare la ricerca binaria standard se l’intero array è ordinato (il primo elemento è rigorosamente più piccolo dell’ultimo elemento) e utilizzare altrimenti la ricerca lineare. Per maggiori informazioni vedi Quanto velocemente puoi effettuare una ricerca lineare? discussione su StackOverflow e 10 Ottimizzazioni sull’articolo di ricerca lineare di Thomas A. Limoncelli.

Hovewer, se le query sono frequenti, è ansible ordinare l’array di input in tempo lineare (vedere l’ algoritmo più veloce per l’array di dimensioni N maiuscole per la discussione della posizione M su StackOverflow) nel passaggio di pre-elaborazione e utilizzare la ricerca binaria standard come al solito.

 #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  

Trova l’indice degli elementi nella matrice ordinata ruotata

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