CODEWITHSUNDEEP
c++
MATH000
MATH000

Reputation: 1103

Improving the performance of this search?

Is there way to do the following search using a faster way? The items on A array are sorted in DESC order.

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;
}

Upvotes: 0

Views: 72

Answers (3)

ilotXXI
ilotXXI

Reputation: 1085

You can use std::lower_bound algorithm in your case. It performs binary search with O(log N), as other people wrote. It will be something like this:

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;
}

Upvotes: 5

Joop Eggen
Joop Eggen

Reputation: 109557

A binary search

int left = 0;
int right = items_no; // Exclusive
while (left < right) {
    int mid = (left + right) / 2;

    if (value == A[mid])
        return mid;
    if (value < A[mid]) {
        left = mid + 1;
    } else {
        right = mid;
    }
}
return only_exact_match ? -1 : right - 1; // The greater

Upvotes: 1

Nikos Kazazakis
Nikos Kazazakis

Reputation: 792

Because your array is sorted, you can search in steps, akin to a bisection. First, check the midpoint against your value. If it's equal, you have your answer. If it's greater, your value is in the lower half of the array. If not, your value is on the upper half. Repeat this process by bisecting the remaining elements of the array until you find your value, or run out of elements. As for your second if clause, if no matching value is found, the closest smaller element is element i+1, if that exists (i.e. you are not at the end of the array).

Upvotes: 1

Related Questions