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?

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