recherche tableau indexé optimisé pour plus-que le nombre

Question

J'ai un tableau de nombres triés:

pts = [ 0, 4, 25, 51, 72, 100 ] 

Compte tenu de la valeur T, je dois trouver l'index du premier numéro dans le tableau supérieur à T.

if T = 2, then the correct index is 1 for value 4 

solution stupide

Je peux le faire avec une recherche linéaire, mais je voudrais optimiser.

exemples non solution de travail

algorithme de recherche binaire trouver l'index d'un nombre exact ..

Y at-il une technique proposée pour résoudre ce genre de problème de recherche? Merci!

Answer 1

algorithme de recherche binaire pour trouver t telle que list[t] <= T et list[t+1] > T (ou t+1 est plus longue que la longueur de la liste)

Answer 2

algorithmes binaires de recherche ne trouvent généralement une correspondance exacte, mais l'algorithme est simple, et il faut soyez facile pour vous de le modifier pour trouver le premier nombre plus grand qu'un nombre donné. Y a-t-il une langue particulière dans laquelle vous cherchez une solution?

Answer 3

La recherche binaire fonctionnera pour cela.

Généralement, une implémentation renverra un nombre négatif pour vous informer du point d'insertion. Par exemple en Java, juste -1-n et vous avez votre position.