Föreläsning 6: Binärsökning

• Inläsning från fil till lista
• Linjär sökning i lista
• Binärsökning i lista
• Komplexitet för binärsökning

  Inläsning från fil till lista

  Vi tänker oss att filen data.reg innehåller personnummer och namn med en person per rad. Vi kan läsa in den i en lista på följande sätt.

  datafil=file("data.reg")  # En textfil
  rader=datafil.readlines() # En lista av raderna i filen
  n=len(rader)              # Antalet rader
  

  Om första raden i filen består av ordet "gurka" kommer lurigt nog rader[0] att bli gurka\n, alltså med ett radbytestecken sist. Om man vill bli av med radbytena och med eventuella blanktecken kan man göra så här:

  for i in range(n):
      rader[i]=rader[i].strip()
  

  Linjär sökning i lista

  Att söka efter en person bland n personer kan ta lång eller kort tid beroende på hur stor otur man har. I genomsnitt måste man kolla n/2 personer innan man hittar den rätta. Om man söker efter någon som inte finns måste man alltid kolla alla n personerna innan man kan ge upp.

  Dessa båda tal anger komplexiteten för algoritmen linjär sökning. Genomsnittlig komplexitet är n/2 och värstafallskomplexiteten är n. Om man använder en for-slinga är det viktigt att bryta den så snart man funnit vad man söker, annars blir det alltid värstafallskomplexitet!

      for person in personer:
  	if pnr == person[:11]
  	    print person[11:]
              break
  

  Om listan är ordnad på personnummer finns en mycket snabbare algoritm som heter binär sökning.

  Binärsökning i lista

  Jag tänker på ett ord i ordlistan. Kan du gissa vilket?
  LAT
  Nej, det kommer före LAT.
  FUL
  Nej, det kommer efter FUL.
  - - - (femton gissningar senare) - - -
  SJUTTON
  Rätt! Det tog sjutton gissningar.
  Det finns knappt tvåhundratusen ord i SAOL (Svenska Akademiens Ordlista). Den första gissningen LAT kommer i mitten och därmed skärs antalet möjliga ord ner till hälften. Eftersom antalet ord i SAOL är ungefär 2 höjt till 17 är man nere i ett enda möjligt ord efter sjutton halveringar.

  Metoden kallas binärsökning och kräver att listan som man ska söka igenom är sorterad.

  Vid binär sökning ska man alltid börja söka i mittersta element i listan.Om det man söker i listan är mindre än elementet så skippar man den del av listan som innehåller element som är större än elementet och man söker igen på samma sätt igenom den del av listan amn har kvar. Men om det man söker är större än elementet så skippar man den del av listan som innehåller elementer som är mindre än elementet och man fortsätter och söker igen på samma sätt på den del av listan som man har kvar. Men det mittersta elementet är det man söker så avbryter man sökningen.

  här nedan är en kod för att söka ett tal i en lista med binärsökning.

  
  # anta att vi har följande ordnad lista med alla tal 
  lista=[1,3,5,8,12,15,17,19,40,50,57,59,90]
  # och vi söker efter talet 57
  s=57
  v=0
  h=len(lista)-1
  while v <= h :
      m=(v+h)/2
      if s < lista[m]:
         h=m-1
      elif s > lista[m]:
         v=m+1
      else:
         print "hittad"
         break
     
  

  Komplexitet för binärsökning

  Om vektorns längd är N kommer binärsökningen att kräva ungefär logN jämförelser. Här betyder log tvålogaritm, dvs log 2 = 1, log 4 = 2, log 8 = 3,..., log 1000 = ca 10, log 1000000 = ca 20 etc.

  Tvålogaritmen är inte ett heltal, men bör avrundas nedåt om man frågar efter genomsnittskomplexitet och avrundas uppåt om man frågar efter värsta fallets komplexitet.

  ---

  Upp till kurssidan.
  

  ---

  Sidansvarig: <vahid@nada.kth.se>
  Senast ändrad 9 november 2004
  Tekniskt stöd: <webmaster@nada.kth.se>