Find the closest number to each given number

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 
#include 
#include 
#include 
using namespace std;

int main(){
    int nbBlocs;
    cin >> nbBlocs;
    int dens;
    std::vector tab(nbBlocs);
    for(int i=0; i> dens;
        tab[i]=dens;
    }
    sort(tab.begin(), tab.end());
    int nbQ;
    cin >> nbQ;
    int quest;
    for(int j = 0; j> 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;
    }

}

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 it1.

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 tab(nbBlocs);
for(int i=0; i> dens;
    tab[i]=dens;
}

Could be turned into:

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

Looking at:

for(int j = 0; j> 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.

StackExchange Code Review Q#108338, answer score: 10