1740 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

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.

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 > 2 => välj höger halva)

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