通用二進制搜索++

我想編寫模板二進制搜索算法，其可以的QList使用arbitary比較器中的模板類型搜索的模板類型元件，這樣：通用二進制搜索++

template<typename T,typename compare_less> 
static int binary_search(QList<T>* list, T target) { 
    int low = 0; 
    int high = list->count()-1; 
    while (low <= high) { 
     int middle = low + (high - low)/2; 
     if (compare_less(*target, *list[middle])) 
      high = middle - 1; 
     else if (compare_less(*list[middle],*target)) 
      low = middle + 1; 
     else 
      return middle; 
    } 
    return low;

}

現在我怎樣才能正確地實現這一點，以使其與QDateTime *模板參數一起工作？我想調用的函數是這樣的：

int index = binary_search<QDateTime*, ???>(dateTimeList,date);

哪裏dateTimeList是類型的QList的，日期是類型QDateTime的*和我真的沒有任何線索在問號的地方寫。

有人可以幫助我正確實現算法，並告訴我如何調用這些參數的算法？

來源

2012-12-12 user1728778

如果Qt documentation有效，則不應執行任何操作。只需在列表的.begin（）和.end（）中使用std :: binary_search，並且如果需要實現比較器，那麼將其傳遞給STL算法。

來源

2012-12-12 16:37:40

問題是afaik，std :: binary_search返回-1，如果找不到元素，但我想返回索引，元素應該插入到哪裏。 – user1728778

因此，使用std :: lower_bound（http://www.cplusplus.com/reference/algorithm/lower_bound/）。如果你不想插入重複項，你可能需要添加一個相等的測試，但它會給你你所需要的。 –

感謝您的建議。現在我試圖使用std :: lower_bound，但編譯器抱怨說，lower_bound不是std的成員。我包括'使用命名空間標準;'在開始。可能是什麼問題呢？ – user1728778

通用二進制搜索++

回答

相關問題