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