通用二进制搜索++

我想编写模板二进制搜索算法，其可以的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

通用二进制搜索++

回答

相关问题