algorithm
Ricerca
Ricerca…
Ricerca binaria
introduzione
La ricerca binaria è un algoritmo di ricerca Dividi e Conquista. Usa O(log n) tempo per trovare la posizione di un elemento in uno spazio di ricerca dove n è la dimensione dello spazio di ricerca.
La ricerca binaria funziona dimezzando lo spazio di ricerca ad ogni iterazione dopo aver confrontato il valore target con il valore medio dello spazio di ricerca.
Per utilizzare la ricerca binaria, lo spazio di ricerca deve essere ordinato (ordinato) in qualche modo. Le voci duplicate (quelle che vengono confrontate come uguali in base alla funzione di confronto) non possono essere distinte, sebbene non violino la proprietà di Ricerca binaria.
Convenzionalmente, usiamo meno di (<) come funzione di confronto. Se a <b, restituirà true. se a non è minore di b e b non è minore di a, aeb sono uguali.
Domanda di esempio
Sei un economista, piuttosto cattivo. Ti viene dato il compito di trovare il prezzo di equilibrio (cioè il prezzo dove offerta = domanda) per il riso.
Ricorda che più alto è il prezzo impostato, più grande è l'offerta e minore è la domanda
Poiché la tua azienda è molto efficiente nel calcolare le forze del mercato, puoi ottenere istantaneamente l'offerta e la domanda in unità di riso quando il prezzo del riso è fissato ad un certo prezzo p .
Il tuo capo desidera il prezzo di equilibrio APPENA POSSIBILE, ma ti dice che il prezzo di equilibrio può essere un numero intero positivo che è al massimo 10^17 e che è garantito che ci sia esattamente 1 soluzione intera positiva nell'intervallo. Quindi vai avanti con il tuo lavoro prima di perderlo!
È consentito chiamare le funzioni getSupply(k) e getDemand(k) , che faranno esattamente ciò che viene indicato nel problema.
Esempio Spiegazione
Qui il nostro spazio di ricerca è compreso tra 1 e 10^17 . Quindi una ricerca lineare è impossibile.
Tuttavia, notate che mentre il k sale, getSupply(k) aumenta e getDemand(k) diminuisce. Pertanto, per ogni x > y , getSupply(x) - getDemand(x) > getSupply(y) - getDemand(y) . Pertanto, questo spazio di ricerca è monotono e possiamo usare la ricerca binaria.
Il seguente psuedocode dimostra l'uso della ricerca binaria:
high = 100000000000000000 <- Upper bound of search space
low = 1 <- Lower bound of search space
while high - low > 1
mid = (high + low) / 2 <- Take the middle value
supply = getSupply(mid)
demand = getDemand(mid)
if supply > demand
high = mid <- Solution is in lower half of search space
else if demand > supply
low = mid <- Solution is in upper half of search space
else <- supply==demand condition
return mid <- Found solution
Questo algoritmo viene eseguito in tempo ~O(log 10^17) . Questo può essere generalizzato al tempo ~O(log S) dove S è la dimensione dello spazio di ricerca poiché ad ogni iterazione del ciclo while , abbiamo dimezzato lo spazio di ricerca ( da [basso: alto] a [basso: medio] o [mid: high] ).
C Implementazione della ricerca binaria con ricorsione
int binsearch(int a[], int x, int low, int high) {
int mid;
if (low > high)
return -1;
mid = (low + high) / 2;
if (x == a[mid]) {
return (mid);
} else
if (x < a[mid]) {
binsearch(a, x, low, mid - 1);
} else {
binsearch(a, x, mid + 1, high);
}
}
Ricerca binaria: sui numeri ordinati
È più semplice mostrare una ricerca binaria sui numeri usando lo pseudo-codice
int array[1000] = { sorted list of numbers };
int N = 100; // number of entries in search space;
int high, low, mid; // our temporaries
int x; // value to search for
low = 0;
high = N -1;
while(low < high)
{
mid = (low + high)/2;
if(array[mid] < x)
low = mid + 1;
else
high = mid;
}
if(array[low] == x)
// found, index is low
else
// not found
Non tentare di tornare presto confrontando l'array [mid] con x per l'uguaglianza. Il confronto extra può solo rallentare il codice. Nota che devi aggiungere uno a basso per evitare di rimanere intrappolato dalla divisione intera sempre arrotondando per difetto.
È interessante notare che la versione precedente della ricerca binaria consente di trovare la più piccola occorrenza di x nell'array. Se la matrice contiene duplicati di x, l'algoritmo può essere leggermente modificato in modo da restituire l'occorrenza più grande di x semplicemente aggiungendo al condizionale if:
while(low < high)
{
mid = low + ((high - low) / 2);
if(array[mid] < x || (array[mid] == x && array[mid + 1] == x))
low = mid + 1;
else
high = mid;
}
Nota che invece di fare mid = (low + high) / 2 , potrebbe essere una buona idea provare mid = low + ((high - low) / 2) per implementazioni come le implementazioni Java per ridurre il rischio di ottenere un overflow per ingressi veramente grandi.
Ricerca lineare
La ricerca lineare è un semplice algoritmo. Passa attraverso gli elementi fino a quando non viene trovata la query, il che rende un algoritmo lineare - la complessità è O (n), dove n è il numero di elementi da passare.
Perché O (n)? Nella peggiore delle ipotesi, devi passare attraverso tutti gli elementi.
Può essere paragonato a cercare un libro in una pila di libri - li passi tutti fino a trovare quello che vuoi.
Di seguito è una implementazione Python:
def linear_search(searchable_list, query):
for x in searchable_list:
if query == x:
return True
return False
linear_search(['apple', 'banana', 'carrot', 'fig', 'garlic'], 'fig') #returns True
Rabin Karp
L'algoritmo Rabin-Karp o l'algoritmo Karp-Rabin è un algoritmo per la ricerca di stringhe che utilizza l'hashing per trovare uno qualsiasi di stringhe di pattern in un testo. La sua media e il miglior tempo di esecuzione è O (n + m) nello spazio O ( p), ma il suo caso peggiore è O (nm) dove n è la lunghezza del testo e m è la lunghezza del pattern.
Implementazione dell'algoritmo in java per la corrispondenza delle stringhe
void RabinfindPattern(String text,String pattern){
/*
q a prime number
p hash value for pattern
t hash value for text
d is the number of unique characters in input alphabet
*/
int d=128;
int q=100;
int n=text.length();
int m=pattern.length();
int t=0,p=0;
int h=1;
int i,j;
//hash value calculating function
for (i=0;i<m-1;i++)
h = (h*d)%q;
for (i=0;i<m;i++){
p = (d*p + pattern.charAt(i))%q;
t = (d*t + text.charAt(i))%q;
}
//search for the pattern
for(i=0;i<end-m;i++){
if(p==t){
//if the hash value matches match them character by character
for(j=0;j<m;j++)
if(text.charAt(j+i)!=pattern.charAt(j))
break;
if(j==m && i>=start)
System.out.println("Pattern match found at index "+i);
}
if(i<end-m){
t =(d*(t - text.charAt(i)*h) + text.charAt(i+m))%q;
if(t<0)
t=t+q;
}
}
}
Mentre calcoliamo il valore di hash, lo dividiamo per un numero primo per evitare la collisione. Dopo aver diviso per il numero primo le probabilità di collisione saranno minori, ma c'è una possibilità che il valore hash possa essere lo stesso per due stringhe, quindi quando abbiamo una partita che dobbiamo controllare carattere per carattere per assicurarci di avere una corrispondenza adeguata.
t = (d * (t - text.charAt (i) * h) + text.charAt (i + m))% q;
Questo è per ricalcolare il valore di hash per il pattern, prima rimuovendo il carattere più a sinistra e quindi aggiungendo il nuovo carattere dal testo.
Analisi della ricerca lineare (peggiore, media e migliore)
Possiamo avere tre casi per analizzare un algoritmo:
Caso peggiore
Caso medio
Caso migliore
#include <stdio.h> // Linearly search x in arr[]. If x is present then return the index, // otherwise return -1 int search(int arr[], int n, int x) { int i; for (i=0; i<n; i++) { if (arr[i] == x) return i; } return -1; }/ * Programma driver per testare le funzioni sopra * /
int main() { int arr[] = {1, 10, 30, 15}; int x = 30; int n = sizeof(arr)/sizeof(arr[0]); printf("%d is present at index %d", x, search(arr, n, x)); getchar(); return 0; }
Analisi dei casi peggiori (solitamente eseguita)
Nell'analisi del caso peggiore, calcoliamo il limite superiore del tempo di esecuzione di un algoritmo. Dobbiamo conoscere il caso che causa il numero massimo di operazioni da eseguire. Per la ricerca lineare, il caso peggiore si verifica quando l'elemento da cercare (x nel codice precedente) non è presente nell'array. Quando x non è presente, le funzioni search () la confrontano con tutti gli elementi di arr [] uno per uno. Pertanto, la complessità temporale del caso peggiore della ricerca lineare sarebbe Θ (n)
Analisi del caso medio (a volte eseguita)
Nell'analisi del caso medio, prendiamo tutti gli input possibili e calcoliamo il tempo di calcolo per tutti gli input. Sommare tutti i valori calcolati e dividere la somma per il numero totale di input. Dobbiamo sapere (o prevedere) la distribuzione dei casi. Per il problema della ricerca lineare, supponiamo che tutti i casi siano distribuiti uniformemente (incluso il caso in cui x non è presente nell'array). Quindi sommiamo tutti i casi e dividiamo la somma per (n + 1). Di seguito è riportato il valore della complessità media del caso.
Analisi dei casi migliori (Bogus)
Nella migliore delle ipotesi, calcoliamo il limite inferiore del tempo di esecuzione di un algoritmo. Dobbiamo conoscere il caso che causa il numero minimo di operazioni da eseguire. Nel problema di ricerca lineare, il caso migliore si verifica quando x è presente nella prima posizione. Il numero di operazioni nel migliore dei casi è costante (non dipende da n). Quindi la complessità temporale nel migliore dei casi sarebbe Θ (1) La maggior parte delle volte, facciamo l'analisi del caso peggiore per analizzare gli algoritmi. Nella peggiore analisi, garantiamo un limite superiore al tempo di esecuzione di un algoritmo che è una buona informazione. L'analisi del caso medio non è facile da fare nella maggior parte dei casi pratici e raramente viene eseguita. Nell'analisi del caso medio, dobbiamo conoscere (o prevedere) la distribuzione matematica di tutti i possibili input. L'analisi del caso migliore è falsa. Garantire un limite inferiore su un algoritmo non fornisce alcuna informazione come nel caso peggiore, un algoritmo potrebbe richiedere anni per essere eseguito.
Per alcuni algoritmi, tutti i casi sono asintoticamente uguali, cioè non ci sono casi peggiori e migliori. Ad esempio, Unisci ordinamento. Unisci Ordina esegue le operazioni Θ (nLogn) in tutti i casi. La maggior parte degli altri algoritmi di ordinamento ha casi peggiori e migliori. Ad esempio, nell'implementazione tipica di Ordinamento rapido (dove pivot viene scelto come elemento d'angolo), il peggiore si verifica quando l'array di input è già ordinato e il migliore si verifica quando gli elementi di pivot dividono sempre l'array in due metà. Per l'ordinamento di inserimento, il caso peggiore si verifica quando l'array viene ordinato in ordine inverso e il caso migliore si verifica quando l'array viene ordinato nello stesso ordine dell'output.