python - Quickly find first entry with a value below or equal -

let's in python have list of files respective sizes, represented dict (i don't care structure, can propose one):

from random import randint  def gen_rand_fileslist(nbfiles=100, maxvalue=100):     fileslist = {}     in xrange(nbfiles):         fileslist["file_"+str(i)] = randint(1, maxvalue)     return fileslist  fileslist = gen_rand_fileslist(10) 

example fileslist:

{'file_0': 2,  'file_1': 21,  'file_2': 20,  'file_3': 16,  'file_4': 12,  'file_5': 67,  'file_6': 95,  'file_7': 16,  'file_8': 2,  'file_9': 5} 

now want find highest value below specified threshold. example:

get_value_below(fileslist, threshold=25) # result should 'file_1' value 21 

the function get_value_below() called in tight loop, should fast possible, , threshold can specified (so sorting doesn't directly).

is there way faster walking through whole list (linear time)?

it depends on how going search threshold in fileslist. if going more Θ(log n) queries, it's better sort first , perform binary search each query. otherwise, if want perform 1 query only, yes it's better linear search since element want can virtually anywhere , you'll need visit each element of list.

if planning use sorting first , binary searching then, use bisect_right input x, return position in list contains biggest element lower or equal x.