Przeszukiwanie binarne, zły wynik

0

Hej
Ćwiczę sobie algorytmy, niestety z jakiegoś powodu nic mi nie chce działać

Próbowałam napisać przeszukiwanie binarne, ale zamiast indeksu liczby szukanej (szukam liczby 2 pod indeksem 6) zwraca liczbę 2 :(


#include <iostream>


int szukaj(int * tablica, int poczatek, int koniec, int x) {
    if (poczatek <= koniec) {
        int srodek = poczatek + koniec / 2;
    
        if (tablica[srodek] == x) {
            return x;
        }
        else if (tablica[srodek] > x) {
            return szukaj(tablica, poczatek, srodek - 1, x);
        }
        else {
            return szukaj(tablica, srodek + 1, koniec, x);
        }
    }
    else {
        return -1;
    }
}


int main()
{
    int tab[10] = {1, 9, 8, 0, -5, 2, 6, 1, 7, 13};
    
    std::cout << szukaj(tab, 0, 10, 2) << std::endl;
    
    return 0;
}

Czy pomoże ktoś znaleźć błąd?

5
        if (tablica[srodek] == x) {
            return x;
        }

Zwraca co mu każesz

1

@Karmela Szutowicz:
Testowałaś to porządnie? Czy ta:
int srodek = poczatek + koniec / 2;
Robi to co Chcesz?

6

Przeszukiwanie binarne to się na ** posortowanej ** tablicy robi :)

0
int szukaj(int * tablica, int poczatek, int koniec, int x) {
    if (poczatek <= koniec) {
        int srodek = poczatek + koniec / 2;

        if (tablica[srodek] == x) {
            return srodek;
        }
        else if (tablica[srodek] > x) {
            return szukaj(tablica, poczatek, srodek - 1, x);
        }
        else {
            return szukaj(tablica, srodek + 1, koniec, x);
        }
    }
    else {
        return -1;
    }
}

   int tab[10] = {-5, 0, 1, 1, 2, 6, 7, 8, 9, 13};
   std::cout << szukaj(tab, 0, 10, 2) << '\n';

Poprawiłam, ale nie działa
Chyba jednak nie robi się na posortowanej, bo dalej nie działa, a poza tym byłoby to bez sensu
I co mam niby źle w int srodek = poczatek + koniec / 2; ??

2

(poczatek + koniec) / 2

a poza tym byłoby to bez sensu

Dlaczego?

4

I co mam niby źle w int srodek = poczatek + koniec / 2; ??

Tak jak zapisałaś, to dzielenie jest tylko robione na zmiennej * koniec *

Chyba jednak nie robi się na posortowanej, bo dalej nie działa, a poza tym byłoby to bez sensu

No jednak się robi https://pl.wikipedia.org/wiki/Wyszukiwanie_binarne
Nie żebym uważał wiki za wyrocznię, ale wszędzie znajdziesz informację, że wyszukiwanie binarne robi się na posortowanych zbiorach liczb :)

Kodzik:

#include <iostream>


int szukaj(int * tablica, int poczatek, int koniec, int x) {
    if (poczatek <= koniec) {
        int srodek = (poczatek + koniec) / 2;

        if (tablica[srodek] == x) {
            return srodek;
        }
        else if (tablica[srodek] > x) {
            return szukaj(tablica, poczatek, srodek - 1, x);
        }
        else {
            return szukaj(tablica, srodek + 1, koniec, x);
        }
    }

    return -1;
}

int main()
{
    //"TEST"
    int tab1[10] = {-5, 0, 1, 1, 2, 6, 7, 8, 9, 13};
    std::cout << szukaj(tab1, 0, 9, 2) << '\n';   //zwraca 4, OK
    
    return 0;
}
1

Po kiego tak komplikować?

#include <iostream>
using namespace std;
		
int binsearch(int tb[],int size,int x)
{
	for(int lf=0,rt=size;lf<rt;)
	{
		int mid=(lf+rt)>>1;
		int v=tb[mid];
		if(v>x) rt=mid;
		else if(v<x) lf=mid+1;
		else return mid;
	}
    return -1;
}

int main()
{
    //"TEST"
    int tab1[10] = {-5, 0, 1, 1, 2, 6, 7, 8, 9, 13};
    cout << binsearch(tab1,sizeof(tab1)/sizeof(*tab1),2)<<endl;   //zwraca 4, OK
    cout << binsearch(tab1,sizeof(tab1)/sizeof(*tab1),-10)<<endl;   //zwraca -1, OK
    cout << binsearch(tab1,sizeof(tab1)/sizeof(*tab1),100)<<endl;   //zwraca -1, OK
    return 0;
}
0

Przecież jak mam posortowaną tablicę, to widzę gdzie jest szukana liczba, TO PO CO MI ALGORYTM KTÓRY DZIAŁA TYLKO NA TAKIEJ TABLICY?

0

Nie możecie wrzucać czegoś po polsku?

Miałam niemiecki w szkole

3

Proszę bardzo - pierwszy link z Google: http://www.algorytm.edu.pl/algorytmy-maturalne/wyszukiwanie-binarne.html

I od razu masz, jako pierwsze zdanie:

Algorytm szuka danego elementu w tablicy uporządkowanej (posortowanej)

Ewentualnie analogiczny artykuł z polskiej Wikipedii - https://pl.wikipedia.org/wiki/Wyszukiwanie_binarne, gdzie również masz napisane

Wyszukiwanie binarne – algorytm, który stwierdza, czy szukany element znajduje się w uporządkowanej tablicy

0

DZIĘKUJĘ @ceratto, @kq i @_13th_Dragon za odpowiedzi

Bardzo proszę o pomoc z następującym zadaniem:
Chcę mieć wyszukiwanie binarne, które działa na tablicy nieposortowanej (no bo po co mi tablica posortowana)

mam taki kod

int szukaj(int * tablica, int poczatek, int koniec, int x) {
    if (poczatek <= koniec) {
        int srodek = poczatek + koniec / 2;

        if (tablica[srodek] == x) {
            return x;
        }
        else if (tablica[srodek] > x) {
            return szukaj(tablica, poczatek, srodek - 1, x);
        }
        else {
            return szukaj(tablica, srodek + 1, koniec, x);
        }
    }
    else {
        return -1;
    }
}

Pomógł mi kq to napisać. Nie wiem jak dalej to zrobić żeby działało na nieposortowanych tablicach :(

6

Niestety, zgodnie z tym co napisali przedmówcy, wyszukiwanie binarne jest algorytmem przeszukiwania posortowanego zbioru. Przykładem może być np. książka telefoniczna, gdzie nie "widać od razu" gdzie dana wartość konkretnie się znajduje.

Jeśli musisz przeszukać nieposortowany zbiór, to po prostu zrób to iteracyjnie.

0

Zrobiłabym iteracyjnie, ale nie wiem co to znaczy

2

Po prostu porównujesz kolejne elementy tablicy od pierwszego do ostatniego za pomocą pętli

1
Karmela Szutowicz napisał(a):

...
Masz tablicę 1,9,15 i jeszcze z tysiąc rosnących elementów. Bardzo szybko znajdziesz szukaną liczbę. Np. 15 od razu widać. A jak są pomieszane????? Już nie

int ile_wartosci_tablcy_igly_znajdzie_sie_w_tablicy_sterta(int sterta[],int rozmiar_sterty_wiekszy_od_100000,int igly[],int rozmiar_igly_wiekszy_od_100000)
{
    cout<<"Na potrzeby wyszukiwania "<<rozmiar_igly_wiekszy_od_100000<<" razy zostanie tobie wyświetlone "<<rozmiar_sterty_wiekszy_od_100000<<" liczb"<<endl;
    cout<<"Tablica sterta jest posortowana więc łatwo zobaczysz czy jest tam podana liczba czy nie."<<endl;
    cout<<"Z tym że raz się pomylisz i trzeba będzie zacząć od początku. Zaczynamy."<<endl;
    int count=0;
    for(int i=0;i<rozmiar_igly_wiekszy_od_100000;++i)
    {
        cout<<"Czy `widzisz` wartość "<<igly[i]<<" wsród wartości:";
        for(int s=0;s<rozmiar_sterty_wiekszy_od_100000;++s) cout<<' '<<sterta[s];
        cout<<"? Jeżeli tak naciśni T: ";
        int ch=cin.get();
        if(ch=='T') ++count;
        while(ch!='\n') ch=cin.get();
    }
    return count;
}

Czy teraz jasne czemu potrzebujesz ten algorytm?

5

A tłumacząc od innej strony: jak nie masz żadnego pojęcia, w jaki sposób kolejne elementy tablicy mają się do siebie¹, czyli chcesz coś, co działa na faktycznie dowolnej tablicy, to nie ma cudów — jeśli chcesz znaleźć jakąś wartość, to musisz przeglądać po kolei, być może wszystkie elementy. Bo nie masz jak wykluczyć, że szukana wartość się nie chowa tam, gdzie jeszcze nie spojrzałaś.

Jak masz posortowaną tablicę, i zobaczyłaś że gdzieś jest 18, a gdzieś 569, to wiesz, że pomiędzy nimi 621 nie trafisz. Ale jak nie masz jej uporządkowanej w żaden znany sposób… to jak miałabyś to wiedzieć?

¹ Niekoniecznie nawet są posortowane, chociaż to oczywiście ideał.

1 użytkowników online, w tym zalogowanych: 0, gości: 1