ça veut dire quoi "en moyenne" ???
si je suis tes calculs, 99% des cas demandent 3 tests ou moins, le reste au max jusqu'à 7 tests.
Dans mon approche, dans tous les cas le pire cas est 4.. et dans 99.999999% des cas 3...
Sauf que ceci est à prendre avec une répartition uniforme, et une requête portant sur l'ensemble..
Dans la pratique, il est peu probable que, dans la majeure partie des cas, cette fonction serve à obtenir quelque chose de supérieur à 10^7... (des indices de l'odre du milliard seront plutôt en général utilisés comme des floats, sauf pour des 64 bits, auquel cas l'adaptation de la dichotomie fourni toujours 5 tests dans le pire des cas et 4 en moyenne..)
Donc, dans la "moyenne des cas d'utilisation", tu feras de 4 à 7 tests...
Et sur un 64 bits de 9 à 15...
Partager