0
\$\begingroup\$

It's my first exercise involving the well-known binary search. The problem goes as follows: we are given a sequence of n numbers and we have to answer to t questions, each of which is: “How many numbers in the specified sequence are greater than the i-th element of the sequence?” For example, we have n = 3 and t = 3. Our sequence is 2, 1, 3. And we have to count numbers greater than the first (1), second (2) and third element of our sequence (3). The correct output is “1 2 0”. I've already written some code… but it works only in some cases.

    #include <iostream>
#include <algorithm>

using namespace std;

template<typename T> int binSearch(const T& x, const T* array, size_t size)
{

int l = 0, p = size - 1, s;

while (l <= p)
{

s = (l + p) / 2;

if (array[s] == x)
return s;

if (array[s] > x)
p = s - 1;

else
l = s + 1;
}

return -1;
}

int main(){

    int n, t;

    cin >> n >> t;

    int a[n];

    int a_sorted[n];

    int questions[t];

    for (int i=0; i<n; i++){ cin >> a[i]; a_sorted[i]=a[i]; };

    for (int i=0; i<t; i++) cin >> questions[i];

    sort (a_sorted, &a_sorted[n]);

    for (int i=0; i<t; i++){

        int index=binSearch(a[questions[i]-1], a_sorted, n);

        int count_=n-(index+1);

        cout << count_ << endl;

    }

    return 0;

}

If my question is difficult to understand, feel free to ask for additional information – it wasn't easy to ask too ;)

\$\endgroup\$
1

1 Answer 1

1
\$\begingroup\$

First, the algorithm you're using strikes me as fairly inefficient. At least if I've understood the code, your intent is to have one array of items in original order, and another in sorted order. When you get a query, you find the number at the specified position in the original array, then do a binary search to find the same item in the sorted array.

I guess if the intent is specifically to write a binary search, that's all right, but if your intent is really to carry out such queries quickly, this doesn't seem like the best approach. Instead, I'd create a more direct mapping from input position to result.

For one possible way to do this, you could create an array of pairs of input values and the position at which that value was entered:

typedef std::pair<int, size_t> input;

std::vector<input> inputs;

int temp;
size_t i = 0;

while (std::cin >> temp)
    inputs.emplace_back(temp, i++);

Then we can sort the inputs (preferably in descending order) based on the input number:

std::sort(inputs.begin(), inputs.end(), 
    [](input a, input b) {
        return a.first > b.first;
    });

Then (the interesting part) we create our lookup table to give the result for a query directly:

std::vector<size_t> query_table(inputs.size());

for (int i=0; i<inputs.size(); i++)
   query_table[inputs[i].second] = i;

Then handling a query is something like:

size_t query(size_t input_pos) { 
    return query_table[pos];
}

Looking at the code in your question, the first thing that sticks out is indentation (or lack thereof). In binSearch, you seem to have no indentation at all. In main, you have a little indentation, but most of your loops and such have the controlled statement on the same line as the loop header, which most C and C++ programmers find distasteful (to put it mildly).

You're also depending on using a variable length array (your int a[n]; andint a_sorted[n];`) which isn't part of C++ (though some compilers include it as an extension).

Looking specifically at the algorithm you're using for your binary search, it appears that it'll potentially give incorrect answers whenever your input contains duplicate values. It simply looks for any instance of the correct value in the sorted array, but since you only want the number of inputs that were large, it should be looking for the position of the last entry with that value. For example: if your input were [1, 2, 1, 1, 1, 1, 1, 2], the sorted array would be: [1, 1, 1, 1, 1, 1, 2, 2]. Since that has 8 elements, and the first element it looks at is the fourth, it would find the fourth, and you'd then conclude that all the other numbers were larger, so it would say there were four larger numbers. What you really want to find is the last instance of that value, so (in this case) you'd find there are really only two larger values.

\$\endgroup\$
3
  • \$\begingroup\$ FYI, your algorithm currently doesn't handle duplicates either, although it could be modified to do so and still take \$O(n)\$ time. \$\endgroup\$
    – JS1
    Commented Feb 3, 2016 at 5:42
  • \$\begingroup\$ @JSI: Right--the normal assumption here is that the code works as intended, so comments are normally restricted to basically refactoring, not fixing (and most of my answer is intended that way). Since it apparently doesn't really work as intended (but lacks an explanation of how or when it fails) I also included a comment about that, but as a more or less separate point (i.e., the rest of the answer follows the norm for the site of assuming that the intent is to achieve the same result as the code in the question). \$\endgroup\$ Commented Feb 3, 2016 at 13:41
  • \$\begingroup\$ Ok now I see what you did there. \$\endgroup\$
    – JS1
    Commented Feb 3, 2016 at 16:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.