I have a problem from UVA online judge here. I have read it tons of times, and as they said, I have to get the answer really fast. I have used a binary search and std::sort, but I am still having a time error. I don't know any faster way of searching on an array other than binary search. Any feedback please?#include <stdio.h>#include <string>#include <algorithm>int n,q,vec[100000];int inicio,final,medio,busca;int cont;int busquedabinaria(){    //busqueda binaria    std::sort(vec,vec+n);    inicio=0;    final=n-1;    medio=(inicio+final)/2;    while(inicio<=final)    {        if(vec[inicio]==busca)            return inicio;        if(vec[medio]==busca)            return medio;        if(vec[final]==busca)            return final;        medio = (inicio + final) / 2;        if (vec[medio] > busca)            final = medio - 1;        else if (vec[medio] < busca)            inicio = medio + 1;        // found    }    return -1;}int main() {    freopen(in.txt, rt,stdin);    freopen(out.txt, wt,stdout);    while (scanf(%d %d\n,&n,&q)!=EOF && (n!=0 || q!=0)    )    {        for (int i=0;i<n;i++)        {            scanf(%d\n,&vec[i]);        }        printf(CASE# %d:\n,cont+1);        cont++;        while(q--)        {        scanf(%d\n,&busca);            int res=busquedabinaria();            if(res!=-1)            {                while (vec[res-1]==busca && res>0)                {                    res--;                }                printf(%d found at %d\n,busca,res+1);        }            else                 printf(%d not found\n,busca);        }    }    return 0;}
UVA 10474 - Where is the marble? time limit
c++;performance;search;binary search;time limit exceeded
Your solution is slow because it performs the sorting before every binary search! Just move the sorting to the line above theprintf(CASE# %d:\n,cont+1);and you'll see the difference.I also add my solution just to see what's possible to optimize (it uses custom int reader, without sort and the binary search):#include <stdio.h>#include <stdlib.h>#include <string.h>#include <time.h>#define SIZE 16*1024#define N    10001static unsigned int values[N];static int  buffer_size = 0;static int  buffer_pos  = -1;   static char buffer[SIZE];unsigned int readInt(){    unsigned int value  = 0;    unsigned int digits = 0;    char b;    if (buffer_pos == -1)    {        buffer_size = fread(buffer, 1, SIZE, stdin);        buffer_pos  = 0;    }    while(buffer_size > 0)    {        if (buffer_pos == buffer_size)        {            buffer_size = fread(buffer, 1, SIZE, stdin);            buffer_pos = 0;        }        while(buffer_pos < buffer_size)         {                b = buffer[buffer_pos++];                       if (b == '\n' || b == ' ')             {                return value;            }                    else            {                        value = value*10 + (b - '0');                digits++;            }        }    }    return value;}int main(int argc, char **argv){    long time = clock();        char buffer[8192];        setvbuf(stdout, buffer, _IOFBF, sizeof(buffer));             unsigned int  n, q, num, max, min, c = 0;    while(1)    {        c++;        n = readInt();        q = readInt();        if(n==0 && q==0) break;        max = 0;        min = N;        memset(values, 0, N * sizeof(unsigned int));                for(unsigned int i=0; i<n; i++)        {            num = readInt();            values[num]++;            if(num > max) max = num;            if(num < min) min = num;        }        unsigned int pos = 1, temp;        for(unsigned int i=min; i <= max; i++)        {            if(values[i] !=0){                temp = values[i];                values[i] = pos;                pos += temp;            }        }        printf(CASE# %d:\n, c);        unsigned qval;        for(unsigned int i=0; i<q; i++)        {            qval = readInt();            int ret = values[qval];            if(ret == 0)                 printf(%d not found\n, qval);            else                 printf(%d found at %d\n, qval, ret);        }    }    //printf(Time (ms): %ld\n, clock()-time);    return 0;}