Wyszukiwanie binarne - czego mi tu brakuje ?

Question

W tablicy n elementowej za pomoca algorytmu wyszukiwania binarnego wskazac na pozycje szuknej liczby.

Jak dla mnie wszystko super a jednak nie działa :)

#include <iostream>
#include <cstdlib>
#include <time.h>

using namespace std;

int n; //ilosc elementow w tablicy
int i; // licznik dla petli for rysujacej tablice
int no_arr; // wybarny numer ktorego pozycje chcemy poznac
int l; // lewy - pierwszy element talbicy od lewej
int p; // prawy - ostatni element tablicy
int s; // srodkowy - centralny element przedzialu

int main()
{
    srand(time(NULL));
    cout << "Ilu elementowa tablice chcesz stworzyc: " << endl;
    cin >> n;

    int tablica[n];

    cout << "Oto tablica wypelniona losowymi wartosciami posortowanymi rosnaco : " << endl;
    for(i=0;i<n;i++)
    {
        tablica[i]=rand()%10+(i*10);
    }

    for(i=0;i<n;i++)
    {
        cout << "|" << tablica[i] << "|";
    }
    cout << endl;
    l=0; // POCZATEK INSTRUKCJI WYSZUKIWANIA
    p=n-1;
    s=(l+p)/2;

    cout << tablica[l] << " wartosc pierwszego elementu tablicy" << endl;
    cout << tablica[s] << " wartosc centralnego elementu tablicy" <<endl;
    cout << tablica[p] << " wartosc ostatniego elementu tablicy" <<endl;
    cout << "Wprowadz numer: " << endl;
    cin >> no_arr;

    do
    {
    if(no_arr==tablica[s])
        {
            cout << "Element na pozycji " << s << endl;
            break;
        }
        else if (tablica[s]<no_arr)
        {
        l=s+1;
        s=(l+p)/2;
        }
        else
        {
        p=s-1;
        s=(l+p)/2;
        }
    } while (no_arr == tablica[s]);
    cout << "Element na pozycji " << s << endl;
    return 0;
}

Będę wdzięczny za wszelkie wskazówki.

Pozdrawiam,

Witek

Answer 1

wiersz 60

} while (no_arr == tablica[s]); // pętla ma się wykonywać gdy warunek JEST SPEŁNIONY czyli powinno być:

} while (no_arr != tablica[s]); // wykonujemy jeśli NIE RÓWNA SIĘ

Answer 2

Pokombinowałem trochę (podpatrzyłem gdzie indziej) i udało mi się to ruszyć jednak nie wiem teraz jak instrukcję if, ktorą umieściłem na samym końcu włączyć w 'główny moduł obliczeniowy'. :(

#include <iostream>
#include <cstdlib>
#include <time.h>

using namespace std;

int n; //ilosc elementow w tablicy
int i; // licznik dla petli for rysujacej tablice
int no_arr; // wybarny numer ktorego pozycje chcemy poznac
int l; // lewy - pierwszy element talbicy od lewej
int p; // prawy - ostatni element tablicy
int s; // srodkowy - centralny element przedzialu

int main()
{
    srand(time(NULL));
    cout << "Ilu elementowa tablice chcesz stworzyc: " << endl;
    cin >> n;

    int tablica[n];

    cout << "Oto tablica wypelniona losowymi wartosciami posortowanymi rosnaco : " << endl;
    for(i=0;i<n;i++)
    {
        tablica[i]=rand()%10+(i*10);
    }

    for(i=0;i<n;i++)
    {
        cout << "|" << tablica[i] << "|";
    }
    cout << endl;
    l=0; // POCZATEK INSTRUKCJI WYSZUKIWANIA
    p=n-1;
    s=(l+p)/2;

    cout << tablica[l] << " wartosc pierwszego elementu tablicy" << endl;
    cout << tablica[s] << " wartosc centralnego elementu tablicy" <<endl;
    cout << tablica[p] << " wartosc ostatniego elementu tablicy" <<endl;
    cout << "Wprowadz numer: " << endl;
    cin >> no_arr;

    while (l<=p)
    {
        s=(l+p)/2;

        if(no_arr==tablica[s])
            {
                cout << "Element " << no_arr << " znajduje sie na pozycji " << s+1 << endl;
                break;
            }
            else if (tablica[s]<no_arr)
            {
            l=s+1;
            }
            else
            {
            p=s-1;
            }
    }

    if (no_arr==tablica[s])
        {
            cout << "Brawo!"<< endl;
        }
        else
        {
            cout << "Nie znaleziono elementu w tablicy " << endl;
        }

    return 0;
}

 

Answer 3

Chodzi Ci o szukanie konkretnego elementu ?

Najprościej możesz zrobić to tak, że posortujesz tablicę, wyznaczysz środkowy element i w zależności od tego, czy liczba jest większa, czy mniejsza, lecisz na lewo lub prawo od środka. Tyle.

Answer 4

Siema, widze juz jeden blad tablice dynamiczne(takie ktorej wielkosc okreslamy podczas dzialania programu) deklarujemy w ten sposob : int *tablica=new int[n]; odwolujesz sie do tego w petli za pomoca tablica[i] .

Popraw to poki co.

Pozdrawiam

Comments

Rozumiem, że w taki sposób mogę zdefiniować ją przed mainem.

Na etapie definiowania tej tablicy właśnie zastanawiałem się jak to zrobić :) Dzięki wielkie.