c++ 对日期进行二分搜索排序 -> 我需要一个范围(cca)

Question

我对一个文件进行了二分搜索。该文件充满了日志消息，其中每行都以日期开头(日期或根据发生的事件排序)

示例:

• 2011-09-18 09.38.20.123
• 2011-09-18 09.38.20.245
• 2011-09-18 09.38.20.393
• 2011-09-18 09.38.20.400
• 2011-09-18 09.38.20.785

如果我需要找到这个日期，例如:2011-09-18 09.38.20.390，我的二分搜索将找不到完全匹配 - 但我不需要完全匹配，我需要找到最接近的日期(这就是我的立场)。

当前代码将在 2011-09-18 09.38.20.245 和 2011-09-18 09.38.20.393 之间跳转。

我需要一些帮助来修改以下代码，以便获得最接近的数字。在上述情况下，我希望:2011-09-18 09.38.20.245(多总比少好)

BinarySearch::BinarySearch(QString strFileName,QDateTime dtFrom_target,QDateTime dtTo_target)
{

    QFile file(strFileName);
    qint64 nFileSize = file.size();

    int nNewFromPos;
    int nNewToPos;

    nNewFromPos = Search(file, dtFrom_target, nFileSize);
    nNewToPos  = Search(file, dtFrom_target, nFileSize);

    if(nNewFromPos!=-1 && nNewToPos!=-1){
        // now parse the new range

    }
    else{
        // dates out of bound

    }   
}

int BinarySearch::Search(QFile &file, QDateTime dtKey, int nMax) 
{  
    file.open(QIODevice::ReadOnly);
    char lineBuffer[1024];  
    qint64 lineLength;
    QDateTime dtMid;        
    int mid;
    int min; 
    if(!min) min = 0;


   while (min <= nMax) 
   {
       mid=(min+nMax)/2;    // compute mid point.                               
       file.seek(mid);  // seek to middle of file (position based on bytes)
       qint64 lineLength=file.readLine(lineBuffer,sizeof(lineBuffer)); // read until \n or error

       if (lineLength != -1) //something is read
       {
           // validate string begin (pos = 0) starts with date

           lineLength = file.readLine(lineBuffer, 24); //read exactly enough chars for the date from the beginning of the log file


           if(lineLength == 23)
           {
            dtMid = QDateTime::fromString(QString(lineBuffer),"yyyy-MM-dd HH.mm.ss.zzz"); //2011-09-15 09.38.20.192

                if(dtMid.isValid())
                {
                    if(dtKey > dtMid){
                        min = mid + 1; 
                    }
                    else if(dtKey < dtMid){
                        max = mid - 1; // repeat search in bottom half.
                    }
                    else{
                        return mid;     // found it. return position
                    }
                }
            }
       }
   }
   return -1;    // failed to find key
}

Answer 1

尝试实现相当于 std::equal_range 的算法它返回一对结果 std::lower_bound和 std::upper_bound

1. 查找排序范围内第一个不小于该值(下限)的元素的位置
2. 查找排序范围中第一个大于该值(上限)的元素的位置

--

template<typename OutIter>
void ReadLogsInRange(
    std::istream& logStream, Log::Date from, Log::Date to, OutIter out)
{
    Log l = LowerBound(logStream, from);
    *out++ = l;
    while(logStream >> l && l.date < to)
        *out++ = l;
}

完整示例:http://ideone.com/CvIYm