питон: найти значение в пределах диапазона в массиве флоат

Question

У меня есть следующий отсортированный список питона, хотя несколько значений может произойти:

[0.0943200769115388, 0.17380131294164516, 0.4063245853719435, 
0.45796523225774904, 0.5040225609708342, 0.5229351852840304, 
0.6145136350368882, 0.6220712583558284, 0.7190096076050408, 
0.8486436998476048, 0.8957381707345986, 0.9774325873910711, 
0.9832076130275351, 0.985386554764682, 1.0] 

Теперь, я хочу знать, индекс в массиве, где определенное значение может упасть :

Например, значение 0,25 будет падать в индекс 2, так как оно находится между 0,173 и 0,40. Думаю, я могу пройти через список и сделать это в цикле for, но мне было интересно, есть ли лучший способ сделать это, что может быть более эффективным с точки зрения вычислений. Я создаю этот массив один раз, но вам нужно выполнить множество поисков.

Answer 1

>>> vals = [0.0943200769115388, 0.17380131294164516, 0.4063245853719435, 
0.45796523225774904, 0.5040225609708342, 0.5229351852840304, 
0.6145136350368882, 0.6220712583558284, 0.7190096076050408, 
0.8486436998476048, 0.8957381707345986, 0.9774325873910711, 
0.9832076130275351, 0.985386554764682, 1.0] 

>>> import bisect 
>>> bisect.bisect(vals, 0.25) 
2 

Answer 2

Если вы знаете, что список уже отсортирован, тогда решение учебника должно выполнить двоичный поиск. Вы сохраняете две границы индекса, мин и макс. Инициализируйте их до 0 и len - 1. Затем установите mid (min + max)/2. Сравните значение с индексом mid с целевым значением. Если это меньше, установите значение min в середину + 1. Если оно больше, установите max в середину 1. Повторите, пока вы не найдете значение или до max < мин, и в этом случае вы найдете нужный индекс в O (log (n)).