How to efficiently search for a structured numeric array

I have a GB size virtual array that is m by n and for which the higher values ​​are right and up. By virtual I mean that the return values ​​are provided from another program from the given coordinates, but the functions at a given run are unknown to the programmer. It is guaranteed that the given number is in the array.

{now it turns out that such a number is the product of two primes, as well as NP hard}

I took a look at Finding Sorted Numeric Values ​​Effectively but I have no structure of multiple lines that I need to reflect. I tried the "spiral" approach, but sometimes it takes a long time to get through. (Considering more than half of the possible slots) Usually, the lines are at regular intervals, but will be different for each line. Columns tend to have a (different) arithmetic progression. The lines are sorted. The left highest value in the row is less than the leftmost value in the next higher row. The largest value in the row is less than the rightmost value in the next higher row. See Data Examples below. I tried to first exclude the rows that cannot hold the target value and then select the row "average" value of the remaining ones. Do a binary search on that line, then go up or down whichever iswhether the next line is more likely to (guess) have more values ​​in the range or not. The target value will most likely be placed in the possible available slots. Here are some sample data

1008 1064 1120 1176 1232

999 1053 1107 1161 1215

988 1040 1092 1144 1196

975 1025 1075 1125 1175

960 1008 1056 1104 1152

Any ideas please?