Binärsökning

Bloggen The Reinvigorated Programmer gav för ett par dagar sedan dess läsare i uppdrag att skriva en binär sök-algoritm i valfritt språk utan att testa (för annat än syntax-fel) och sedan skicka in. Detta pga en undersökning som visade på att endast 10% av programmerare kan producera en buggfri binär sök-algoritm.

Jag gjorde ett försök och i slutänden kom jag fram till följande funktion:

int binSearch(int a[], int size, int target)
{
  int lowPos = 0, highPos = (size - 1), middlePos = (highPos / 2);
  int returnVal = -1;
  while ((lowPos <= highPos) && (a[middlePos] != target))
  {
    middlePos = (lowPos + highPos) / 2;

    if (target > a[middlePos])
      lowPos =   middlePos + 1;
    else
      highPos =  middlePos - 1;
  }

  if (a[middlePos] == target)
    returnVal = middlePos;

  return returnVal;
}

---

syntax highlighted by Code2HTML, v. 0.9.1

En binär sökning söker igenom en sorterad lista värden och tittar ifall mittenvärdet är högre eller mindre (eller lika med) det sökta värdet, sedan halveras listan till den halva som bör innehålla det sökta värdet (t.ex övre halvan om mittenvärdet är 16 och det sökta värdet är 20). Detta upprepas tills mittenvärdet är lika med det sökta värdet eller den kvarvarande listan är tom.

Tyvärr fixade jag det inte på första försöket (och är inte hundra på att funktionen är buggfri) utan behövde testa och se att min rutin inte fungerade. Jag hamnade i ett så kallat off-by-one-läge, dvs att sökningen stannade ett ifrån det sista elementet (som borde innehålla det sökta värdet ifall det finns i listan).

Nyckeln var att inse att ett mittenelementet som inte är lika med det sökta värdet kan exkluderas. Detta leder till att delningen av listan blir

    if (target > a[middlePos])
      lowPos =   middlePos + 1;
    else
      highPos =  middlePos - 1;

Detta tog mer tid att klura ut än jag vill erkänna, men jag var nöjd när jag äntligen förstod vad och framför allt varför.

The Reinvigorated Programmer håller just nu på att gå igenom lite mer formella metoder för att beskriva algoritmer, det är kul att läsa. hitintills har han gått igenom invarianser och gränsfunktioner. Det är intressant att lära sig lite mer om algoritm-design, jag försöker skriva vad jag vill göra på papper innan jag programmerar men de här metoderna gör det möjligt att bevisa att man gör rätt.

I övrigt är det också en trevlig blogg, mycket programmering men också recensioner av de nya Doctor Who-avsnitten. Jag rekommenderar den varmt.

Ifall någon som kan lite om binär sök-algoritmen snubblar in skulle jag uppskatta att samtliga fel i koden ovan pekades ut.

Etiketter: algoritm, binary sort, binär sortering, the reinvigorated programmer