[C#] Bisekcija

Lp.

Prosim za malo pomoči pri metodi PoisciZBisekcijo. Metoda bi naj vrnila indeks prve pojavitve iskanega elementa, vendar ga ne.

static int PoisciZBisekcijo(int el, int[] a)
        {
            
                int levaStran = 0;
                int desnaStran = a.Length - 1;
                while (levaStran <= desnaStran)
                {
                    int sredina = (levaStran + desnaStran) / 2;//Računanje sredine
                    if (a[sredina] == el)
                    {
                        return sredina;
                    }
                    else if (el < a[sredina])
                    {
                        desnaStran = sredina - 1;
                    }
                    else
                    {
                        levaStran = sredina + 1;
                    }
                }
                return -1;       
        }

Any tips?

Recimo da mam polje {51, 51, 23, 56, ....}. Element ki ga iščem naj bo 51. Vrne mi indeks 1, namesto 0.

Jop. Izrecno je bilo naročeno, da morem uporabit bisekcijo.

Urejen po velikosti. Od najnižjega do najvišjega števila.

Na papir izvedi svojo kodo za arraye dolzine 0, 1, 2, 3, 4, 5
Ustrezno popravi kodo in po vsakem popravku ponovi teste od 0 naprej.

Takole je, tvoja koda ne bo vrnila indeksa prvega elementa. Pač pa (pravilno) indeks iskanega elementa.
Če želiš najti z bisekcijo prvi element, se ne smeš ustaviti, ko najdeš iskani element, ampak ko je iskani interval dolžine 1 (ali 2 z nekaj dodatnega dela). Primer: vsi elementi so 51, iščeš 51. Zakaj bi bisekcija vrnila 0, ko je n/2 čisto dovolj dober?

Na voljo imaš več strategiJ.
(1) ko najdeš iskani element, se linearno zapelješ proti levi do prvega manjšega ali do začetka. Slabost: linerana zahtevnost.
(2) Z bisekcijo greš vedno do konca (do intervala dolžine 1), pri čemer paziš, da kakšnega potencialnega kandidata ne izpustiš. Natančneje, ko imaš na sredini zadetek, greš gledat levi interval skupaj s sredino; medtem ko če je na sredini več, greš lahko gledat levi interval brez sredine (ker element na sredini ni več kandidat). Če boš delal preveč naivno, se bo stvar ustavila na intervalu dolžine 2 (oziroma še bolje, ne bo se ustavila, premaknila pa tudi ne)

joze67 je 16. mar 2012 ob 10:53 izjavil:

Spura je 16. mar 2012 ob 10:26 izjavil:

Samo z bisekcijo ne bos nikoli mogel narest da vedno prvega zadane.

Seveda lahko; še več, samo z bisekcijo lahko zagotovi, da bo ta element našel v logaritemskem času. Če se je pripravljen voziti po intervalu (linearen čas), se lahko vozi od začetka in išče iskani element.

Teoretično: med dva zaporedna elementa vstavimo aritmetično sredino sosednjih elementov. Dobimo polje velikosti 2n-1 - natančen premislek pokaže, da je treba nekaj (majhnega) vstaviti še pred prvi element in novo polje je lepo veliko 2n. No, in iščemo ne element x, ampak največji vstavljeni element, ki je manj kot x. Tak je točno eden in bisekcija na novem, večjem polju ga bo našla (s samo enim dodatnim korakom). Iskani element je potem desno od najdenega. QED.

Upam da trollas. A pregledat vse elemente in pregledat ponovljene elemente je isto? Sicer se pa da ampak to zakomplicira algoritem za enga zacetnika ful. V tvojem dokazu ni ocitno, da je nov scenarij enak prejsnjemu.

V povprecju ta algoritem na realnih podatkih pogleda manj kot 2 dodatna elementa.

Problem je že rešen. Vseeno hvala :)

A je ucitelj v novem solskem letu samo malo spremenil nalogo?

Sicer pa si poglej odgovore od lani, ce malo pomislis (kar bos tekom solanja moral veckrat), bos ze stuhtal odgovor, glede na to da je problem samo malo zrcaljen.

Ce pa se vedno ne gre pa natancno povej kaj vse si poskusil in kje se zatakne.