Find the closest number to each given number

Question

I have a program which works but it is a bit too slow with big numbers.

nbBlocs contains the size of the array, it can be up to 20000 and I enter the value inside on each position.

nbQ is the number of queries (at most 20000 queries). For each query, it looks inside the array and tells me which is the closest value to it (by absolute difference). So, if my array is [0,2,5,11,24,32] and the query is 10, it returns 11 because absolute difference (10-11) is the smallest.

Input example

7                    (size of array)
41 32 11 17 24 8 16  (all the values inside array)
4                    (nbQ)
9 20 28 11           (four queries)

Output

8 17 24 11

Here is my code :

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int nbBlocs;
    cin >> nbBlocs;
    int dens;
    std::vector<int> tab(nbBlocs);
    for(int i=0; i<nbBlocs; i++){
        cin >> dens;
        tab[i]=dens;
    }
    sort(tab.begin(), tab.end());
    int nbQ;
    cin >> nbQ;
    int quest;
    for(int j = 0; j<nbQ; j++){
        cin >> quest;
    int valSup=-1;
    int valInf=-1;
    int reponse=-1;
        for(unsigned int i=0;i<tab.size();i++){
            if(quest < tab[i]){
                    valSup = tab[i];
                if(i!=0)
                        valInf = tab[i-1];
                    else
                         valInf = valSup;
                }

        if(i==(tab.size()-1) && valSup == -1){
            valSup = tab[tab.size()-1];
            valInf = valSup;
        }
        if(valSup != -1 && valInf != -1){
            if(std::abs(quest - valSup) < (std::abs(quest - valInf))){
                reponse = valSup;
                break;
            }
            else if (std::abs(quest - valSup) == (std::abs(quest - valInf))){
                reponse = valInf;
                break;
            }
            else{
                reponse = valInf;
                break;
            }
        }
    }
        if (reponse != -1)
        cout << reponse << endl;
    }

}

Answer 1

First point: every time anybody writes code with using namespace std; at global scope, a cute, furry little animal dies a horrible death. You don't want that on your conscience, so you need to stop doing it¹.

Right now, you seem to be doing a linear search. Since you've sorted the numbers, you could do a binary search instead. This could use either std::lower_bound or std::upper_bound. If the target number might be duplicated in the collection, lower_bound gives the location of the first, and upper_bound gives the location of the last of those duplicates. Since it doesn't appear that duplicates would change the results you're producing, you might prefer to just remove the duplicates with std::unique immediately after sorting (but unless you really expect duplicates in the inputs, this may waste more time than it saves).

If you also sort the nbQ numbers before searching for them, you can optimize a little more by reducing the bounds within which you do successive binary searches. Given the relatively small amount of data (20000 numbers, 20000 queries) this probably won't make a huge difference, but still might be fairly noticeable.

Other than that, you could make considerably better use of the standard algorithms and containers than you do right now. For example:

int dens;
std::vector<int> tab(nbBlocs);
for(int i=0; i<nbBlocs; i++){
    cin >> dens;
    tab[i]=dens;
}

Could be turned into:

std::vector<int> tab;
tab.reserve(nbBlocs);
std::copy_n(std::istream_iterator<int>(std::cin), nbBlocs, std::back_inserter(tab));

Looking at:

for(int j = 0; j<nbQ; j++){
    cin >> quest;
int valSup=-1;
int valInf=-1;
int reponse=-1;

[... much more]

The indentation is misleading--based on the indentation, it's not immediately apparent that all the succeeding code is executed inside that loop. This doesn't affect speed in itself, but better formatting could give a better grasp of the importance of speed of the inner loop.

Although it's also unrelated to speed, my final thought would be that your variable names seem open to considerable improvement. A few (e.g., response) aren't too bad, but quite a few (e.g., nbBlocs, nbQ, quest) seem fairly meaningless.

---

^{1. Okay, seriously, it brings a large (and unknown) number of symbols into scope. We know some of those names, but the standards reserve a fair number of other classes of names (e.g., anything starting with str) so the number of other possibilities is infinite. Bottom line: it's unnecessary and dangerous.}

Answer 2

The first part seems OK, you type in the elements and then sort them.

The second part is not so good your checking every element taking O(N), as you have already sorted the data you could use a binary search on the elements in O(log N).

auto iter = lower_bound(tab.begin(), tab.end(), quest);

Now the element is either the iter or the element before iter.