CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 7 of 7
  1. #1
    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.

    Please help.

  2. #2
    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. #3
    Join Date
    Sep 2015
    Posts
    3

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

    Quote Originally Posted by tiliavirga View Post
    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.

  4. #4
    Join Date
    Jun 2015
    Posts
    208

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

    Quote Originally Posted by misharica View Post
    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. #5
    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. #6
    Join Date
    Jun 2015
    Posts
    208

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

    Quote Originally Posted by misharica View Post
    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. #7
    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.

Tags for this Thread

Posting Permissions

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





Click Here to Expand Forum to Full Width

Featured