CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

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

1. Junior Member
Join Date
Sep 2015
Posts
3

## 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.

2. Banned
Join Date
Jun 2015
Posts
208

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

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?
Last edited by tiliavirga; September 28th, 2015 at 09:15 AM.

3. Junior Member
Join Date
Sep 2015
Posts
3

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

Originally Posted by tiliavirga
If the number of dates is reasonably small why not just search through the dates from start to end?
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.

4. Banned
Join Date
Jun 2015
Posts
208

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

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.
Last edited by tiliavirga; September 29th, 2015 at 04:46 AM.

5. Junior Member
Join Date
Sep 2015
Posts
3

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

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

6. Banned
Join Date
Jun 2015
Posts
208

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

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.

7. Elite Member Power Poster
Join Date
Apr 2000
Location
Belgium (Europe)
Posts
4,626

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

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.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•