algorithm
Recherche
Recherche…
Recherche binaire
introduction
La recherche binaire est un algorithme de recherche de division et de conquête. Il utilise l'heure O(log n) pour trouver l'emplacement d'un élément dans un espace de recherche où n est la taille de l'espace de recherche.
La recherche binaire fonctionne en divisant par deux l'espace de recherche à chaque itération après avoir comparé la valeur cible à la valeur intermédiaire de l'espace de recherche.
Pour utiliser la recherche binaire, l'espace de recherche doit être trié (trié) d'une manière ou d'une autre. Les entrées en double (qui se comparent comme étant égales selon la fonction de comparaison) ne peuvent pas être distinguées, bien qu'elles ne violent pas la propriété de recherche binaire.
Classiquement, nous utilisons moins que (<) comme fonction de comparaison. Si un <b, il retournera vrai. si a n'est pas inférieur à b et b n'est pas inférieur à a, a et b sont égaux.
Exemple de question
Vous êtes un économiste, un très mauvais. Vous avez la tâche de trouver le prix d'équilibre (c'est-à-dire le prix où l'offre = la demande) pour le riz.
Rappelez-vous que plus le prix est élevé, plus l'offre est grande et la demande est faible
Votre entreprise étant très efficace dans le calcul des forces du marché, vous pouvez obtenir instantanément l'offre et la demande en unités de riz lorsque le prix du riz est fixé à un certain prix p .
Votre patron veut le prix d'équilibre ASAP, mais vous dit que le prix d'équilibre peut être un nombre entier positif d'au plus 10^17 et qu'il y a exactement 1 solution entière positive dans l'intervalle. Alors lancez-vous dans votre travail avant de le perdre!
Vous êtes autorisé à appeler les fonctions getSupply(k) et getDemand(k) , qui feront exactement ce qui est indiqué dans le problème.
Exemple d'explication
Ici, notre espace de recherche est compris entre 1 et 10^17 . Une recherche linéaire est donc impossible.
Cependant, notez que lorsque k augmente, getSupply(k) augmente et getDemand(k) diminue. Ainsi, pour tout x > y , getSupply(x) - getDemand(x) > getSupply(y) - getDemand(y) . Par conséquent, cet espace de recherche est monotone et nous pouvons utiliser la recherche binaire.
Le psuedocode suivant illustre l'utilisation de la recherche binaire:
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
Cet algorithme s'exécute dans le temps ~O(log 10^17) . Ceci peut être généralisé à ~O(log S) temps où S est la taille de l'espace de recherche depuis à chaque itération de la while boucle, nous avons réduit de moitié l'espace de recherche ( à partir de [bas: haut] sur [bas: mi] ou [mi: haut] ).
C Implémentation de la recherche binaire avec récursivité
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);
}
}
Recherche binaire: sur des numéros triés
Il est plus facile de montrer une recherche binaire sur des nombres en utilisant un pseudo-code
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
N'essayez pas de revenir plus tôt en comparant le tableau [moyen] à x pour l'égalité. La comparaison supplémentaire ne peut que ralentir le code. Notez que vous devez en ajouter un au plus bas pour éviter de se laisser piéger par une division entière en arrondissant toujours vers le bas.
Fait intéressant, la version de recherche binaire ci-dessus vous permet de trouver la plus petite occurrence de x dans le tableau. Si le tableau contient des doublons de x, l'algorithme peut être légèrement modifié pour qu'il renvoie la plus grande occurrence de x en ajoutant simplement au conditionnel 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;
}
Notez qu'au lieu de faire mid = (low + high) / 2 , il peut également être judicieux d'essayer mid = low + ((high - low) / 2) pour des implémentations telles que les implémentations Java afin de réduire le risque d'obtenir un débordement pour des entrées vraiment importantes.
Recherche linéaire
La recherche linéaire est un algorithme simple. Il parcourt les éléments jusqu'à ce que la requête soit trouvée, ce qui en fait un algorithme linéaire - la complexité est O (n), où n est le nombre d'éléments à parcourir.
Pourquoi O (n)? Dans le pire des cas, vous devez passer par tous les n éléments.
Cela peut être comparé à la recherche d'un livre dans une pile de livres - vous les parcourez tous jusqu'à ce que vous trouviez celui que vous voulez.
Voici une implémentation 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'algorithme de Rabin – Karp ou l'algorithme de Karp – Rabin est un algorithme de recherche de chaîne qui utilise le hachage pour trouver l'un quelconque d'un ensemble de chaînes de motif dans un texte. Son temps moyen et meilleur est O (n + m) dans l'espace O ( p), mais le pire des cas est O (nm) où n est la longueur du texte et m la longueur du motif.
Implémentation d'algorithme en Java pour la correspondance de chaîne
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;
}
}
}
Lors du calcul de la valeur de hachage, nous la divisons par un nombre premier afin d'éviter les collisions. Après la division par nombre premier, les chances de collision seront moindres, mais il est possible que la valeur de hachage soit identique pour deux chaînes. nous obtenons un match que nous devons vérifier caractère par caractère pour nous assurer que nous avons un match correct.
t = (d * (t-text.charAt (i) * h) + text.charAt (i + m))% q;
Il s'agit de recalculer la valeur de hachage pour le motif, d'abord en supprimant le caractère le plus à gauche, puis en ajoutant le nouveau caractère du texte.
Analyse de la recherche linéaire (pires, moyens et meilleurs cas)
Nous pouvons avoir trois cas pour analyser un algorithme:
Pire cas
Cas moyen
Meilleur cas
#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; }/ * Programme pilote pour tester les fonctions ci-dessus * /
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; }
Pire analyse de cas (habituellement faite)
Dans le pire des cas, nous calculons la limite supérieure du temps d'exécution d'un algorithme. Nous devons connaître le cas qui entraîne le nombre maximal d'opérations à exécuter. Pour la recherche linéaire, le pire des cas se produit lorsque l'élément à rechercher (x dans le code ci-dessus) n'est pas présent dans le tableau. Lorsque x n'est pas présent, la fonction search () la compare avec tous les éléments de arr [] un par un. Par conséquent, la complexité temporelle la plus défavorable de la recherche linéaire serait Θ (n)
Analyse de cas moyenne (parfois effectuée)
Dans une analyse de cas moyenne, nous prenons toutes les entrées possibles et calculons le temps de calcul pour toutes les entrées. Sommez toutes les valeurs calculées et divisez la somme par le nombre total d'entrées. Nous devons connaître (ou prédire) la distribution des cas. Pour le problème de recherche linéaire, supposons que tous les cas sont uniformément distribués (y compris le cas où x n'est pas présent dans le tableau). Nous somme donc tous les cas et divisons la somme par (n + 1). Voici la valeur de la complexité du temps moyen.
Meilleure analyse de cas (Bogus)
Dans le meilleur des cas, nous calculons la limite inférieure sur le temps d'exécution d'un algorithme. Nous devons connaître le cas à l'origine du nombre minimum d'opérations à exécuter. Dans le problème de la recherche linéaire, le meilleur cas se produit lorsque x est présent au premier emplacement. Le nombre d'opérations dans le meilleur des cas est constant (non dépendant de n). Donc, dans le meilleur des cas, la complexité du temps serait Θ (1) La plupart du temps, nous effectuons une analyse des pires scénarios pour analyser les algorithmes. Dans la pire des analyses, nous garantissons une limite supérieure sur le temps d'exécution d'un algorithme, ce qui est une bonne information. L'analyse de cas moyenne n'est pas facile à faire dans la plupart des cas pratiques et elle est rarement réalisée. Dans l'analyse de cas moyenne, nous devons connaître (ou prédire) la distribution mathématique de toutes les entrées possibles. L'analyse des meilleurs cas est fausse. Garantir une limite inférieure sur un algorithme ne fournit aucune information, car dans le pire des cas, un algorithme peut prendre des années.
Pour certains algorithmes, tous les cas sont asymptotiquement identiques, c’est-à-dire qu’il n’ya pas de pire et de meilleur cas. Par exemple, Fusionner le tri. Fusionner le tri fait les opérations Θ (nLogn) dans tous les cas. La plupart des autres algorithmes de tri ont les pires et les meilleurs cas. Par exemple, dans l'implémentation classique du tri rapide (où pivot est choisi comme élément d'angle), le pire se produit lorsque le tableau en entrée est déjà trié et le meilleur lorsque les éléments pivotants divisent toujours le tableau en deux moitiés. Pour le tri par insertion, le pire des cas se produit lorsque le tableau est trié en sens inverse et que le meilleur cas se produit lorsque le tableau est trié dans le même ordre que la sortie.