Fastest way to query randomly in a big database in java

I am using JDBC to query data in Java. In my Mysql database there are more columns but only two significant: ID,time. The columns are sorted sequentially (so for ID 1-Time 1, 2-2 etc..). I have 36000 rows at this data set, but this can vary.

The task is that I have to query a single row from the table where the time's row value equals with a given random time from 1 to 36000. (for example: random time:3200 I have to return the 3200th row, for 3 the third row etc..)

First I thought about SELECT * from db where time=randomtime, but it takes too much time when I want to get more rows.

My second thought was to create an little interval around the random number (for example: the number is 15, the left bound is 5 and the right bound is 25). I would save this to a cache which is a LinkedHashMap and I would use LRU caching strategy. So for number 15 i would create an interval, cache it, for another random number I would check if the cache contains that number, if so I return from the LinkedHashMap, if not I query another interval and add it to the cache.

Is this idea a good solution for this problem or it can be done better? Any answers are appreciated. Have a nice day.