提高此搜索的性能？

Question

有没有办法用更快的方式进行以下搜索？A数组上的项目按DESC顺序排序.

int find_pos(int A[], int value, int items_no, bool only_exact_match)
{
    for(int i = 0; i < items_no; i++)
        if(value == A[i] || (value > A[i] && !only_exact_match))
            return i;

    return -1;
}

Answer 1

你可以std::lower_bound在你的情况下使用算法.正如其他人写的那样,它用O(log N)执行二进制搜索.它将是这样的:

int find_pos(int A[], int value, int items_no, bool only_exact_match)
{
    const int *pos_ptr = std::lower_bound(A, A + items_no, value, std::greater<int>());
    const ptrdiff_t pos = pos_ptr - A;

    if (pos >= items_no)
        return -1;
    if (*pos_ptr != value && only_exact_match)
        return -1;
    return pos;
}