If I understand you right, your problem was the power on time, if the EEPROM was almost full.

Then a search like a binary tree starting from the half of the EEPROM size should be fast enough.


I use my approach for a data logger, where all former records should also be important. And then the search time during power on plays no role, since it can be done in the background whereas new records collected temporary into the RAM.


Peter