I'd also want to try interpolation search for this (not necessarily linear interpolation since we're doing floats) - you can take much better guesses than "it's in the middle somewhere" by not having to look at the data through a 1-bit-wide pinhole as comparison algorithms do.

A better starting point is: use a better language. Python is terrible and unbearably slow. If you need anything serious or performant, switch to something else.