find closest date in sorted array of dates if required date is missing

Hi everyone,
here is my problem.

I have a sorted array of dates that is stored in a circular buffer. I have a pointer to last date in buffer. There is a possibility that some dates are missing. Client requires a range of dates. If low limit date is missing, program should return first closest date that is higher then required one and vice versa for upper limit date.
Here is an example:

Dates in circular buffer (int[18]):
1,2,3,4,5,11,12,13,14,15,21,22,23,24,25,26,27,28
and if client wants from 8 to 23,
program should return 11,12,13,14,15,21,22,23.

I tried like this :
(if I detect that I will just go x steps forward and x steps backward I split x in half)

buffer | diff | pointer

1,2,3,4,5,11,12,13,14,15,21,22,23,24,25,26,27,28 -20 (28)
*
1,2,3,4,5,11,12,13,14,15,21,22,23,24,25,26,27,28 +7 (1)
*
1,2,3,4,5,11,12,13,14,15,21,22,23,24,25,26,27,28 -5 (13)
*
1,2,3,4,5,11,12,13,14,15,21,22,23,24,25,26,27,28 +5 -> (5/2)+1=+3 (3)
*
1,2,3,4,5,11,12,13,14,15,21,22,23,24,25,26,27,28 -3 -> (-3/2)-1=-2 (11)
*
1,2,3,4,5,11,12,13,14,15,21,22,23,24,25,26,27,28 +4 (4)
*
1,2,3,4,5,11,12,13,14,15,21,22,23,24,25,26,27,28 -5 (13)
*

If we continue like this we will get 3,11,4,13 over and over again.

Note:
It is only coincidence that we get 11 here. When I use some real examples, with more dates,
this algorithm jumps over some other 4 (or 3) numbers.

Please help.

If the number of dates is reasonably small why not just scan linearly through the dates. First from start up to the lower limit and then onward up to the upper limit?

Quote:

---

Originally Posted by tiliavirga

If the number of dates is reasonably small why not just search through the dates from start to end?

---

Hi, thank you for answer.
I suggested some random dates just to illustrate a problem. In real life, I have 12000 dates stored in EEPROM memory of some device, and every reading takes a few seconds. So actual problem is that I have to find a date with minimum possible readings.

Quote:

---

Originally Posted by misharica

So actual problem is that I have to find a date with minimum possible readings.

---

Okay, since the dates are sorted you can find the lower limit by way of a binary search. With 12000 dates it will be 14 accesses (2^14 = 16384) at the most.

Then dates follow in order from lower to upper limit so the number of additional accesses will be the same as the number of dates inside the range.

Hello.
Binary search worked great for me. I am sorry I did not replay earlier. Thanks a lot!

Quote:

---

Originally Posted by misharica

Binary search worked great for me.

---

Nice to hear that. The challenge must've been to make the sorted sequence appear straight to the binary search although the circular buffer wraps it around. But I guess it can be fixed with a quite straightforward access transformation.

since the table is fixed size, and in eprom (and thus not changing) minimum access would make me think a an appropriate hash based on a linear function would reduce accesses by a lot.

finding a decent matching function could take a while though, so not sure it's going to be beneficial for 12K items (which would need 13 accesses)

Slightly easier maybe would be to modify the binary search to not split the range in half each time, but instead split it proportionally of the date you're searching for compared to the date of the lowest and highest item. This would work very well if the dates in the table are fairly evenly distributed and could work against you if they're highly clustered.

As is usual in programming. The regular binary search is a good general solution to a problem. If you know your data ahead of time (which you do, since it's in eprom), you can tailor code to make use of the inate knowledge you have about how the data is structured.