CODEWITHSUNDEEP
c++templatessearchbinary
user1728778
user1728778

Reputation: 151

generic binary search in c++

I'd like to write a template binary search algorithm, which can search a template type element in a template type QList using an arbitary comparator, like this:

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;

}

Now how can I implement this correctly in order to make it work with QDateTime* template parameters? I'd like to call the function like this:

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

Where dateTimeList is of type QList, date is of type QDateTime* and I really don't have any clue what to write in the place of question marks.

Can someone help me implement the algorithm correctly and show me how to call the algorithm with these arguments?

Upvotes: 0

Views: 2914

Answers (1)

Harper Shelby
Harper Shelby

Reputation: 16583

You shouldn't have to implement anything, if the Qt documentation is valid. Just use std::binary_search with your list's .begin() and .end(), and if you need to implement a comparator, do so and pass it to the STL algorithm.

Upvotes: 5

Related Questions