[C++] Wyszukiwanie binarne

[mario765i]

Witam! Od niedawna zacząłem przygodę z programowaniem. Mam do napisania program w języku C++ (używam CodeBlocks). Oto jego treść:

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 niemniejszych niż xi.

Wejście: W pierwszej linii dana jest liczba n (1 ≤ n ≤ 1000000), oznaczająca długość tablicy. Następnie dane jest n nieujemnych liczb w kolejności niemalejącej, które stanowią zawartość tablicy. W drugiej linii dana jest liczba m (1 ≤ m ≤ 1000000), oznaczająca ilość zapytań. Następnie danych jest m liczb xi.
Wyjście: Dla każdego z m zapytań wypisz odpowiedź - ilość liczb niemniejszych od liczby x z zapytania.

Przykład:
Dla danych wejściowych
10 3 4 8 11 23 54 996 8710 911147 10001010
10 1 0 8 64 99 114 334 8484 41 911147
poprawną odpowiedzią jest
10 10 8 4 4 4 4 3 5 2

Oto napisany przeze mnie kod:

Kod: Zaznacz cały

#include<iostream>
using namespace std;

int main()
{
    int n, i;
    cin >> n;
    int a[n];

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

    int m, j;
    cin >> m;
    int b[m];

    for (j=0; j<m; j++)
    {
        cin >> b[j];
    }

    for (j=0; j<m; j++)
    {
        if (b[j]<=a[0]) cout << n << " ";
        else
        {
            int k=0;
            for (i=n-1; i>=0; i--)
            {
                if (a[i]<b[j]) break;
                else k++;
            }
            cout << k << " ";
        }
    }

    return 0;
}

Program działa poprawnie, ale gdy wysyłam go na sprawdzarkę, to dostaje komunikat "time limit exceeded". I tu jest moja prośba, czy mógłby ktoś poprawić mój kod, tak aby przeszedł test sprawdzarki.

[wawek91]

Zatytułowałeś temat 'wyszukiwanie binarne' tak więc mam pytanie, gdzie w swoim kodzie masz zaimplementowany algorytm wyszukiwania binarnego? Nie ma go tam. Wiesz na jakiej zasadzie to działa? Twój program (o ile się nie mylę) działa kwadratowo, natomiast wyszukiwanie binarne ma złożoność logarytmiczna więc stąd ten komunikat. Jeśli nie wiesz jak zaimplementować wyszukiwanie binarne to pomogę, ale najpierw sam spróbuj.

[mario765i]

Dzięki za wskazówkę. Napisałem funkcję wyszukiwania binarnego. Oto ona:

Kod: Zaznacz cały

// Funkcja sprawdza, czy x znajduje sie w tablicy "tablica"
// począwszy od komórki tab[a] do komórki tab[b]
bool binary_search(int x, int *tab, int a, int b)
{
	while (a != b)
	{
		int m = (a+b)/2;
		if (tab[m] < x)
			a  = m+1; // szukaj od med+1 do high
		else
			b = m;   // szukaj od low do med
	}
	if ( tab[a] == x ) return true;
	return false;
}

Tylko teraz nie wiem jak tę funkcję wykorzystać do tego programu (jak wspomniałem dopiero zacząłem programować i póki co niewiele potrafię). Tak więc proszę o dalszą pomoc.

[adambak]

Dzięki za wskazówkę. Napisałem funkcję wyszukiwania binarnego. Oto ona:

Kod: Zaznacz cały

// Funkcja sprawdza, czy x znajduje sie w tablicy "tablica"
// począwszy od komórki tab[a] do komórki tab[b]

Tobie niestety nie wystarczy sama informacja o tym, czy iks znajduje się w tablicy czy nie.. interesuje Cię na której pozycji znajduje się iks (i to nie w ogólności, ale taki o najmniejszym indeksie, bo może ich być kilka wg specyfikacji).. zauważ, że dzięki takiej informacji będziesz mógł wypisać na wyjście wartość: \(\displaystyle{ n-index}\), gdzie index jest najmniejszym indexem szukanej liczby w tablicy a[].. bo skoro znajduje się on na takim miejscu to wszystkie liczby w następnych komórkach tablicy są od niego niemniejsze (zważywszy na to że dostajesz na wejściu posortowaną tablicę).. prawda, że widać jaki zysk? tak to robiłeś w pesymistycznym przypadku \(\displaystyle{ n}\) kroków w pętli, żeby zliczyć wszystkie niemniejsze liczby od danej, a teraz zapuścisz binary_search o złożoności \(\displaystyle{ \log n}\) i masz odpowiedź, jest dużo lepiej.. popraw kod aby funkcja zwracała najmniejszy indeks szukanej liczby w tej tablicy (czyli ma być typu int) i zadanie gotowe.. jak czegoś nie rozumiesz to pytaj, na koniec będę miał dla Ciebie jeszcze parę wskazówek odnośnie zadań

[mario765i]

Jeśli dobrze zrozumiałem, to chodzi Ci o taką funkcję:

Kod: Zaznacz cały

// Funkcja znajduje minimalny wskaźnik j (a <= j <= b), dla którego
// tab[j] >= x
int lower_bound(int x, int *tab, int a, int b)
{
	while (a != b)
	{
		int m = (a+b)/2;
		if (tab[m] < x)
			a  = m+1; // szukaj od m+1 do b
		else
			b = m;   // szukaj od a do m
	}
	if ( tab[a] >= x ) return a;
	return a+1;
}

I dalej nie wiem jak to razem połączyć.

[adambak]

Super! no to teraz służę pomocą, dobrze że powalczyłeś samemu, teraz wystarczy dla wczytywanego \(\displaystyle{ b[j]}\) wypisać wartość: n - lower_bound(b[j], a, 0, n-1), czy to jest jasne? najlepiej na jakimś małym przykładzie na kartce sobie rozpisz.. a teraz obiecane wskazówki:

1) to co wcześniej pisałem - dla każdej wczytanej danej od razu licz wynik i go wypisuj.. zobacz że robisz niepotrzebnie 2x taką samą pętlę od 0 do m.. szkoda dodatkowej pamięci i czasu..
2) poczytaj o scanf/printf, są znacznie szybsze niż cin/cout (które są wygodne) i dla pewności na internetowych sprawdzarkach używaj zawsze ich - będziesz miał pewność, że chodzi o za wolny algorytm (w przypadku TLE) a nie o coś innego..
3) piszesz w Cpp, więc poczytaj o STLu i jak może Ci pomóc..
4) chyba tyle..

moja propozycja kodu po poprawkach:

Kod: Zaznacz cały

#include<iostream>
#include<cstdio>
using namespace std;

// Funkcja znajduje minimalny wskaźnik j (a <= j <= b), dla którego
// tab[j] >= x
int lower_bound(int x, int *tab, int a, int b)
{
  while (a != b)
  {
    int m = (a+b)/2;
    if (tab[m] < x)
      a  = m+1; // szukaj od m+1 do b
    else
      b = m;   // szukaj od a do m
  }
  if ( tab[a] >= x ) return a;
  return a+1;
}

int main()
{
  int n,i,m,j,b;
  scanf("%d",&n);
  int a[n];

  for (i=0; i<n; i++)
    scanf("%d", &a[i]);

  scanf("%d",&m);
  for (j=0; j<m; j++)
  {
    scanf("%d",&b);
    printf("%d
",n-lower_bound(b,a,0,n-1));
  }
  return 0;
}

a teraz wersja wykorzystująca STL:

Kod: Zaznacz cały

#include<iostream>
#include<algorithm>
#include<vector>
#include<stdio.h>

using namespace std;

int main()
{
  int n,i,b,m,j;
  vector<int>a;
  vector<int>::iterator it;

  scanf("%d",&n);
  for(i=0; i<n; i++)
  {
    scanf("%d",&b);
    a.push_back(b);
  }

  scanf("%d",&m);
  for (j=0; j<m; j++)
  {
    scanf("%d",&b);
    it=lower_bound(a.begin(), a.end(), b);
    printf("%d
",int(a.end()-it));
  }
  return 0;
}

zobacz, że jest krócej (a mogłoby być jeszcze krócej).. no ale takie rzeczy warto używać jak już się je umie samemu napisać - w celu zaoszczędzenia czasu.. dlatego najpierw chciałem, żebyś sam napisał binarne parę razy i je zrozumiał, potem można się wspierać STLem.. wszystko co potrzebne do tego jest tutaj:

Kod: Zaznacz cały

http://www.cplusplus.com/reference/stl/

jak czegoś nie rozumiesz to pisz..
powodzenia w dalszym kodzeniu..

[mario765i]

Dzięki za pomoc nad tym programem. Bez problemu przeszedł test sprawdzarki. Dzięki również za udzielone wskazówki, na pewno poczytam i przemyśle je. Jeszcze raz wielkie dzięki.