If you're going to pre-compute, pre-compute also a look-up table for your ordered data. I wrote something like this for a simple flat-binary key-value store [1] (that table is computed into RAM on start-up).
That way you jump from look-up table to look-up table, and then search the remaining space with something like a binary search.
That way you jump from look-up table to look-up table, and then search the remaining space with something like a binary search.
[1] https://gitlab.com/danbarry16/u-database