# Recherche d'une paire d'éléments dans une liste

## I. Le sondage
Classez les différentes solutions de la plus efficace (1) à la moins efficace (4).

|Nom (facultatif)|déclarative|opérationnelle naïve|opérationnelle boucles imbriquées|opérationnelle dichotomie|
|:-:|:-:|:-:|:-:|:-:|
|Bruno M|* | * | * | * |
|Serge B| 2 | 3 | 4 | 1 |
|JB B| 1 | 3 | 4 | 2 |
|L.L| 1 | 3 | 3 | 2 |
|Grégory| 1 | 3 | 4 | 2 |

## II. Les remarques

### 1. Bruno M
Ici, n'hésitez pas à rajouter une partie à votre nom avec vos propres commentaires (justification de votre classement, intérêt ou non de la chose, critique de telle ou telle solution proposée...)
### 2. Serge B
Au feeling sans vraiment d'idée sur la déclarative.
### 3. JB B
Je suis assez sûr de moi pour la complexité asymptotique (et donc pour $n$
supérieur à, disons, un million). L'opérationnelle naïve est sans doute plus rapide que la version dichotomique jusqu'à des valeurs de $n$ relativement grandes.
### 4. LL
La première est linéaire, la dernière quasi-linéaire, les deux autres quadratiques mais sont pour moi relativement identiques, j'ai souvenir que le built-in in n'est pas si impressionant que cela.
Au passage:
Il existe un math.prod à partir de Python 3.8 pour éviter le reduce prod.
Pour éviter de refaire la dichotomie, il existe le module bisect.
### Serge B
En fait je ne suis presque sûr que de la 3 (boucles imbriquées) qui est probablement la plus lente. Je pense que la dicho c'est bien mais la naive avec if nb2 in l1, c'est du Python donc ça doit être pas mal aussi. J'hésite entre les deux. Pas d'idée sur la 1.
### Grégory
J'avoue avoir cherché sur le web la complexité de l'intersection d'ensembles avant de répondre. Du coup, je viens de comprendre pourquoi les ensembles et les dictionnaires sont notés pareil en Python... c'est pratiquement la même chose !
La version dichotomique en n°2 si n est suffisamment grand. Ensuite, le test "in" de Python sera plus rapide que rechercher3 (codé en C ?).
Merci pour cet exemple intéressant.