Ca fait un peu longtemps que j'ai fini mes études, et j'ai eu tous les types de profs imaginables.
 
J'ai le souvenir encore frais qu'un jour on m'a dit qu'une recherche dichotomique  était encore plus optimisée si au lieu de couper l'espace de recherche à la moitié, on le coupe au tiers. (a chaque itération)
 
Je me souviens d'une preuve au tableau basée sur les suites géométriques statistiques. Ca se tenait, et en pratique ca marchait.
 
Mais maintenant que tout ca est loin derrière moi, j'aimerai retrouver un papier la dessus... est ce que l'un de vous aurais un lien, ou pourrait faire la preuve de cette hypothèse ?
 
En plus, c'est bon à ajouter dans vos algo, il suffit de changer un 2 en 3...

la complexité d'un parcours  est de l'ordre du log ( en base 2 ) , multiplié par le cout de chaque comparaison

si tu coupe en 3 , tu vas avoir un cout de l'ordre du log ( en base 3 ) multiplié par le cout de comparaison , tu gagne donc

mais l'avantage de couper en deux c'est que tu as d'un côté ce qui est plus grand et de l'autre ce qui est plus petit . Comment tu coupe en 3 , sans que le cout de l'opérateur de comparaison n'explose ?  

Tu gagne certes mais l'operateur de selection en 3 parties doit avoir une méchante geule.

hmpf, je viens de comprendre vos réponses par rapport à la question en haut.
 
j'avais compris qu'il coupait toujours en 2, avec un rapport 1/3 et 2/3, de façon à, quand on a de la chance, virer les 2/3 d'un coup.
 
sauf que déjà j'étais pas convaincu du gain, mais surtout je pigeais pas pourquoi vous trouviez ça compliqué (puisque dans ce cas c'est toujours > ou < )
 
bon, je retourne hiberner

sinon, pour un tri dans un tableau avec pivot (quicksort) , on prefere coupé par nu pivot pris au hasard que de couper 'exactement' en deux  
c'est ce que qui donne les meilleurs resultats

oui mais bon, y a toujours que 2 morceau et donc le sélecteur est simple.

exactement,  et coupé au 1/3 apporte les mêmes contraintes que couper au 1/2 , ca change rien , ce sera toujours moins bon  que de couper au pifomètre

C'est pas tout à fait ca, on ne coupe pas en 3, au coupe à 1 tiers !!!
 
On a ce qui est plus petit 1/3   d'un coté, et ce qui est plus grand 2/3 de l'autre.
 
Mais vous venez de me rappeler que le quicksort utilise un pivot aléatoire...
Enfin, le coup du 1/3 2/3  c'est toujours bon à prendre dans les algo embarqué ou on ne peut pas avoir de fonction rand... (dans les shaders par exemple)

alors pas d'interet  
mieux vaut faire confiance au chaos et couper au hasard

sauf quand il n'y a pas de rand dispo comme le dit nounours

pas de rand, tu coupe en 2 c'est strictement pareil.

(après, je ne me prononce pas sur l'éventuelle optimisation du 1/3 2/3, nounours a l'air sûr de lui, même si ça me semble étrange, pour moi ça ne fait qu'augmenter l'écart type des ittérations, sans en changer la moyenne)

exactement.

Sinon si tu as n éléments tu peux couper en n, comme ça t'as qu'une itération... Mais n tests Couper en 2, 3 ou plus, c'est une histoire de compromis entre le temps nécessaire pour une itération, qui augmente avec le nombre de morceaux, et la profondeur moyenne de la recherche, qui diminue avec le nombre de morceaux.

 
La blague c'est que l'exemple classique de méta-prog, c'ets le tri à bulle sur N valeurs entièrement déroulé. Ca ressemble à ça, et on voit que tant que N < 10 on gagne genre 20%

Je suis pas sur de bien comprendre votre histoire:
- couper en 2, en faisant 2 comparaisons, tu peux choisir parmi 4
- couper en 3, en faisant 2 comparaisons, tu peux choisir parmi 3
- couper en 4, en faisant 3 comparaisons, tu peux choisir parmi 4
 
euh, c'est moi, ou bien couper en 2 c'est la meilleure façon ? Parce qu'à diviser par n > 2, tu perds progressivement l'avantage de la dichotomie plus n grandit

wof méta ou pas, quand tu implémentes un tri, dès que tu passes sur N petit, un tri par insertion ou de même complexité, ça casse tout. j'irais quand meme pas à faire un bulle