binær, sekventiel søgning

I forbindelse med hvilke former for datastrukturer??

Kunne være arrays eller hægtede lister, sorterede eller usorterede.
Faktisk drejer det sig om at vi på vores uddannelse skulle have haft noget materiale om det, men det halter \"lidt\". Derfor er spørgsmålet rettet mod noget generelt om disse søgninger

Du kan lave sekventiel søgning i begge dele. Rent faktisk kan du kun lave sekventiel søgning i en enkelthægtetliste. Det er jo ikke muligt at hoppe fra element til element, da \"adressen\" ikke kendes.

En sekventiel søgning er i sagen natur, at du starter i den ene ende og læser et element eller tabelingang ad gangen indtil du enten finder det du søger efter, eller at du når enden af listen eller tabellen.

Den binære søgning kan udføres i sorterede tabeller eller i binære søgetræer.

Grundprincippet er for sådan ens for de to ting. Men håndteringen og optimeringen af søgetræer kan være lidt tricky (hvorfor jeg ikke vil komme ind på det).

Princippet i en binær søgning grundlæggende den, at du hele tiden halve den mængde data du vil søge i.

Dette sker ved, at du start med at gå til midten af din tabel.
Ser om du er ved den værdi du leder efter. Hvis ikke så leder du videre i den del af tabellen som kan indeholder den eftersøgte værdi.

Nedenstående illustrer en sorteret tabel med 13 ingange indeholdende heltal,
hvor du gerne vil se om tallet 20 eksistere (du har valgt dig af runde op, når du finder midten)

1 søgning  1|2|5|7|9|12|15|18|19|20|45|49|52
                        x   

2 søgning  18|19|20|45|49|52
                    x

3 søgning  |18|19|20
                x

4 søgning  20
            x

Der er gået koks i mine X

de skal stå som følger

1 : 15
2: 45
3: 19
4: 20

såfremt en tabel ikke er sorteret kan du kun lede den igennem sekventielt for at være sikker på, at du ikke har misset noget

Tak, lige hvad jeg (og de andre i klassen) havde brug for!

codemon

bare for at være nysgerrig hvilken skole / uddannelse