在已排序的日期数组中查找日期的算法
在已排序的日期数组中查找日期的算法
提问于 2015-09-28 19:51:50
这就是我的问题。
我有一个有序的日期数组，它存储在一个循环缓冲区中。我有一个指向缓冲区中最后一个日期的指针。有可能某些日期丢失了。客户端需要一个日期范围。如果缺少下限日期，程序应返回高于所需日期的第一个最近日期，反之亦然。
下面是一个示例：
循环缓冲区(Int18)中的日期：
1,2,3,4,5,11,12,13,14,15,21,22,23,24,25,26,27,28
如果客户端想要从8到23，程序应该返回11,12,13,14,15,21,22,23。
我试过这样做：
备注：
两颗星之间的
- number是当前日期，diff是查找8的步骤数。
- 指针不能小于0或大于17。
{1,2,3,4,5,11,12,13,14,15,21,22,23,24,25,26,27,*28*}, diff = -20
{*1*,2,3,4,5,11,12,13,14,15,21,22,23,24,25,26,27,28}, diff = +7
{1,2,3,4,5,11,12,*13*,14,15,21,22,23,24,25,26,27,28}, diff = -5
{1,2,*3*,4,5,11,12,13,14,15,21,22,23,24,25,26,27,28}, diff = +5 -> (5/2)+1=+3<br />
(if I detect that I will just go x steps forward and x steps backward I split x in half)
{1,2,3,4,5,*11*,12,13,14,15,21,22,23,24,25,26,27,28}, diff = -3 -> (-3/2)-1 = -2
{1,2,3,*4*,5,11,12,13,14,15,21,22,23,24,25,26,27,28}, diff = 4
{1,2,3,4,5,11,12,*13*,14,15,21,22,23,24,25,26,27,28}, diff = -5
{1,2,*3*,4,5,11,12,13,14,15,21,22,23,24,25,26,27,28}, diff = +5 -> (5/2)+1=+3如果我们继续这样下去，我们将一次又一次地得到13,3,11,4。
备注：
，
- ，这只是巧合，我们在这里得到了11。当我使用一些真实的例子，有更多的日期，这个算法跳过其他4(或3)个numbers.
- Dates存储在uC的EEPROM中，所以读取日期需要一段时间，我需要尽可能快地找到日期(读取次数最少)。
请帮帮忙。
回答 1
Stack Overflow用户
发布于 2015-09-28 19:59:37
将p1设置为缓冲区的开始，将p2设置为结束。X就是你要找的。
如果p1Date的日期在X之后，则返回p1。如果p2Date在X之前，则返回p2。
看看p1和p2，m之间的中点，如果mDate在X之后，那么p1=m就是p2=m。
重复此操作，直到p1=p2。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/32822318
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号