Ile liczb w tablicy

Question

Witam, mam takie zadanie:

Masz daną posortowaną tablicę liczb nieujemnych nie dłuższą niż milion elementów. Dla każdego zapytania o liczbę x odpowiedz, ile liczb w tej tablicy jest nie mniejszych niż xi.

Mój kod:

#include <iostream>
using namespace std;
int tab[1000002];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,m,z,l=0;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>tab[i];
    }
    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>z;
        for(int j=0;j<n;j++){
            if(z<=tab[j])
                l++;
        }
        cout<<l<<' ';
        l=0;
    }
    return 0;
}

Czy można przyśpieszyć bardziej ten program? Jest może inny algorytm nie liniowy żeby wykonywał się szybciej?

Z góry dzięki za podpowiedzi.

Answer 1

Dane w tablicy są posortowane, więc możesz spokojnie zastosować lekko zmodyfikowany algorytm Binary Search, który ma wydajność logarytmiczną.

Comments

Mam coś takiego ale nie wiem jak dokładnie to przerobić.

#include <iostream>
using namespace std;
int tab[1000002];
int b(int n,int z);
int main()
{
    int n,m,z,p;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&tab[i]);
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        scanf("%d",&z);
        p=b(n,z);
        printf("%d ",p);
    }
    return 0;
}
int b(int n,int z)
{
    int l;
    int p = n-1;
    while(l<=p)
    {
        l=0;
        int sr = (l + p)/2;

        if(tab[sr] == z){
            p=sr+1;
            l++;
        }
        return l;

        if(tab[sr]>z)
            p = sr - 1;
        else
            l = sr + 1;
}

    return 0;
}

Bo myślałem nad tym że jeżeli tab == z to idziemy w górę i sprawdzamy czy się nie powtarza, ale nie wiem jak to dokładnie zrobić.