La función de búsqueda binaria de Python busca el primer número en una lista ordenada mayor que un valor específico

Estoy tratando de escribir una función en Python que encuentre el primer número en una lista ordenada mayor que un valor específico que pase como argumento. He encontrado ejemplos en línea que utilizan entendimientos de listas simples para lograr esto, pero para mis propósitos, necesito realizar esta operación con frecuencia y en listas grandes, por lo que una búsqueda que se realice en tiempo lineal es demasiado costosa.

Me ha costado escribir una función de búsqueda binaria iterativa para lograr esto, aunque me estoy topando con algunos casos en los que no funciona correctamente. Por cierto, la función no es necesaria para tratar un caso en el que no hay un elemento más grande en la lista. Aquí está mi función existente:

def findFirstLarger(num, sortedList): low = 0; high = len(sortedList) - 1 mid = -1 while True: print("low: " + str(low) + "\t high: " + str(high)) if (low > high): print("Ah geez, low is " + str(low) + " and high is " + str(high)) return # debugging, don't want this to happen if low == high: return sortedList[low] else: mid = (low + high) / 2; if num == sortedList[mid]: return sortedList[mid] elif num > sortedList[mid]: low = mid + 1 else: high = mid - 1 

Un caso que he notado donde esta función no funciona es el siguiente:

 >>> somenumbers=[n*2 for n in range(131072)] >>> somenumbers[-5:] [262134, 262136, 262138, 262140, 262142] >>> binsearch.findFirstLarger(262139,somenumbers) low: 0 high: 131071 low: 65536 high: 131071 low: 98304 high: 131071 low: 114688 high: 131071 low: 122880 high: 131071 low: 126976 high: 131071 low: 129024 high: 131071 low: 130048 high: 131071 low: 130560 high: 131071 low: 130816 high: 131071 low: 130944 high: 131071 low: 131008 high: 131071 low: 131040 high: 131071 low: 131056 high: 131071 low: 131064 high: 131071 low: 131068 high: 131071 low: 131070 high: 131071 low: 131070 high: 131069 Ah geez, low is 131070 and high is 131069 

Aquí, el resultado correcto sería 262140 , ya que este es el primer número en la lista mayor que 262139 .

¿Alguien puede recomendar una implementación más limpia de esto que realmente funcione? No pensé que esto sería un problema tan esotérico, aunque todavía no he podido encontrar una solución en ninguna parte.

¿Has probado el módulo bisect ?

 def find_ge(a, key): '''Find smallest item greater-than or equal to key. Raise ValueError if no such item exists. If multiple keys are equal, return the leftmost. ''' i = bisect_left(a, key) if i == len(a): raise ValueError('No item found with key at or above: %r' % (key,)) return a[i] find_ge(somenumbers, 262139) 

Su código es incorrecto en que (1) low > high es un caso de terminación válido. (2) no debe detenerse en low == high , por ejemplo, devolverá un índice incorrecto cuando num == 3 para sus somenumbers .

Si necesita la implementación sin la función bisect, puede probar el siguiente código:

 def findFirstLargerOrEqual(num, sortedList): '''Finds the smallest index in the sortedList of the element which is greater-than or equal to num''' slen = len(sortedList) start = 0 while slen > 0: m = start + slen//2 if sortedList[m] < num: slen = slen - (m+1 - start) start = m+1 continue if start < m and sortedList[m-1] >= num: slen = m - start continue return somenumbers[m] raise ValueError('Not found') somenumbers=[n*2 for n in range(131072)] print(findFirstLargerOrEqual(262139, somenumbers)) #output: 262140