0210 Sökalgoritmer

För betygen E och C förväntas du kan implementera en sökalgoritm. För betyget A förväntas du kunna implementera flera sökalgoritmer.

Öppna projektet sorterinsalgoritmer. Nu ska du lägga till några metoder som söker i vektorn numbers.

Linjär sökning

Metoden printOkIfFound20

Metoden skriver ut ok om talet 20 finns i vektorn numbers.

Metoden has20

Metoden returnerar true om talet 20 finns i vektorn numbers.

Metoden linearSearch

Givet en vektor x med heltal. Jämför vart och ett av elementen med det sökta.

Skriv en metod linearSearch(). Metoden tar det sökta heltalet som parameter. Metoden returnerar index för det funna elementet eller t.ex. -1 om inget element var det sökta. Testa att metoden fungerar.

Linjär sökning med animering - för de som gör staplar

Gör metoderna ovan. Förslag på animering följer.

Alla staplar är röda från början. Färga den som studeras för tillfället blå. Om och när sökt element hittas, färgas den stapeln grön.

Binär sökning

Givet en vektor x med heltal. Sortera vektorn i stigande ordning, från vänster till höger.

  1. Jämför de båda elementen i mitten med det sökta värdet.
  2. Om sökt värde är mindre eller lika med det vänstra mittvärdet, välj den vänstra halvan av vektorn. Annars välj den högra halvan av vektorn.
  3. Upprepa 1 och 2 för den valda halvan av vektorn.
  4. När ett element återstår avslutas sökningen. Är detta element det sökta har sökningen lyckats.

Implementera metoden binarySearch(). Metoden tar det sökta talet som parameter och returnerar index för det funna talet, eller -1 om inget tal hittades.

//Exempel

//vald subvektor är inom parentes

//mittvärden i vald subvektor markeras med fet stil

//sök efter 3

0, 1, 2, 3, 4, 5, 6, 7 (index)

1, 2, 3, 4, 5, 6, 7, 8 (element)

(1, 2, 3, 4, 5, 6, 7, 8) (3 <= 4 => välj vänster halva)

(1, 2, 3, 4), 5, 6, 7, 8 (3 > 2 => välj höger halva)

1, 2, (3, 4), 5, 6, 7, 8 (3 <= 4 => välj vänster halva)

1, 2, (3), 4, 5, 6, 7, 8 (3 är sökt, returnera 2 som är index för 3)

Animerad - för de som gör staplar

Förslag på animering följer nedan.

Alla staplar är röda från början.

Färga bortvalda staplar blå. I exemplet ovan är de bortvalda staplarna de som inte är kvar mellan parenteserna.

Om det sista elementet är det sökta färgas det grönt.