Søgning er grundlæggende

Søgning er en af de grundlæggende opgaver mange programmer skal løse. Man har information lagret på en eller anden form, og ønsker nu at finde en bestemt oplysning, ud fra et givet søgekriterie.

Det rejser to spørgsmål:

Hvordan skal data være organiseret?

Hvad skal et søgekriterie formuleres?

Søge efter nummer Mht. det sidste vil vi indskrænke os til at søge på en indentifikation af vore data, bestående af et nummer. Selv om ordet "nummer" til dels antyder en entydighed, vil vi i det flg. ikke antage, at der kun findes ét element med et givet nummer.

Mht. vores organisation af data, vil det være som integers i et array.

Vi vil i det følgende arbejde med klassen Liste:
Source 1:
Klassen Liste
public class Liste {
  
  private int[] tabel;
  
  public Liste( int[] t ) {
    tabel = t;
  }

  ...
}
Vi vil lave en række metoder til denne klasse, der foretager en søgning, hver på deres måde.

1. Lineær søgning

Lad os først se på den situation, hvor vi ikke kan gøre os nogen antagelse om, at elementerne skulle være ordnet på nogen måde; de ligger i tilfældig rækkefølge.

Figur 1:
Usorteret array

Starte fra en ende af At søge i et sådant array, levner kun en mulighed. Man må starte fra en ende af, og lede igennem arrayet indtil man enten finder det søgte element eller må konstatere at det ikke var der. Altså en simpel iteration over arrayet:

En sådan søgning kan implementeres i Java, med følgende metode i vores klasse Liste:
Source 2:
Lineær søgning
public class Liste {
  
  ...

  public int linearSearch( int value ) {

    for ( int i=0; i<tabel.length; i++ )
      if ( tabel[i] == value )
        return i;

    return -1;
  }

  ...
}
Hvis elementet findes, returnerer metoden index for den første forekomst. Hvis elementet ikke findes returneres -1.

O(n)
I worst case skal hele listen gennemløbes for at finde det ønskede element, altså O(n). Hvis elementet ikke findes skal hele listen altid gennemløbes, før det kan konstateres.

Ikke aftegende orden Hvis tabel i stedet var ordnet i ikke aftagende orden vil vi have mulighed for at forbedre disse søgetider. Når vi nu søger igennem arrayet, kan vi allerede når tallene overstiger det søgte tal, fastslå at det ikke er at finde i arrayet.

Stoppe tidligere Hvis vi f.eks. søger efter 7 i følgende array, kan vi ved element 8 konstatere, at det ikke kan betale sig at søge videre. I eksemplet giver det ikke den store besparelse, men arrayet kunne fortsætte vilkårligt længere efter 9, med endnu større værdier.

Figur 2:
Søgning efter 7 kan stoppe ved 8

Vi opnår altså en forbedring, men i worst case skal hele listen stadig søges igennem for at finde et element (hvis det element vi søger netop er det sidste).

En sådan søgning kan implementeres i Java, med følgende metode i vores klasse Liste:
Source 3:
Lineær søgning i sorteret array
public class Liste {
  
  ...

  public int linearSortedSearch( int value ) {
    int i;
    
    for ( i=0; i<tabel.length; i++ )
      if ( tabel[i] >= value )
        break;
    
    if ( i < tabel.length && tabel[i] == value )
      return i;
    else
      return -1;
  }

  ...
}
Den øgede effektivitet er et beskedent udbytte af, at listen er sorteret. Vi skal i næste afsnit se hvordan det kan udnyttes mere effektivt.

2. Binær søgning

I hverdagen støder vi ofte på sorterede datamængder. F.eks. er ordene i en ordbog ordnet alfabetisk og et opslag efter et ord sker ved at man slår op et sted i bogen, ser at det ikke er det rigtige sted og derefter prøver et andet sted, indtil man finder det søgte ord.

I den lineære søgealgoritme ovenfor udnyttede vi ordningen på følgende måde: Vi startede forrest i bogen og inspicerede hvert eneste ord i ordbogen, indtil vi enten fandt det søgte ord eller kom forbi det sted hvor dette skulle have været.

Manuel søgning i ordbog
Algoritmen kan naturligvis forbedres betydeligt. Når man slår op i en ordbog, bruger man ordningen ved at udelukke den ene del af bogen. Hvis vi f.eks. leder efter ordet "søgning" og slår op under "kalkulation", kan man udelukke den del af ordbogen der indeholder ordene der alfabetisk kommer før "kalkulation". Det er den idé, der bruges i binær søgning.

Halvere resten
Ved binær søgning prøver man at udelukke så meget af arrayet som muligt, hver gang man ser på et af dets elementer. Hvis man tager det midterste element i listen, vil man på grundlag af ordningen af elementerne, kunne udelukke den ene halvdel af arrayet. Hvis man f.eks. søger elementet 34, og det midterste element i arrayet er 42, kan man udelukke, at det befinder sig i den øverste/højre del af arrayet. Man kan så igen vælge det midterste element i det tilbageværende delarray, og hele tiden udelukke den ene halvdel af det tilbageværende.

Lad os se et eksempel. Vi vil finde 3 i følgende tabel:

Figur 3:
Sorteret array

Vi starter med at anføre den del af arrayet som vi vil søge i (det hele) med de to index start og slut. Som udgangspunkt kan det søgte element befinde sig et hvilket som helst sted i dette array. Derfor sætter vi start til 0 og slut til 10 (index for det sidste element). Dernæst beregner vi det midterste element som det der befinder sig i indgangen med index (start+slut)/2 = (0+10)/2 = 5, idet vi anvender heltalsdivision:

Figur 4:
5 er for stor

Det midterste element 5 er for stort. Vi kan derfor fastslå at 3 ikke kan befinde sig i den del af arrayet der går fra index midt og fremefter. Vi flytter derfor slut til midt-1 og beregner det nye midtpunkt som (0+4)/2 = 2:

Figur 5:
2 er for lille

2 er for lille og vi flytter derfor start til midt+1, dvs. index 3. Det nye midtpunkt bliver (3+4)/2=3:

Figur 6:
3 er det søgte element

Her finde vi det søgte element, og søgningen terminerer.

Man kan implementere algoritmen, med følgende metode i vores Liste-klasse:
Source 4:
Binær søgning
class Liste {
  
  ...

  public int binarySearch( int value ) {
    int start = 0;
    int slut = tabel.length - 1;
    int midt = (start + slut) / 2;
    
    while ( start <= slut ) {
      if ( tabel[midt] < value )
        start = midt+1;
      else if ( tabel[midt] > value )
        slut = midt-1;
      else // de er ens
        return midt;
        
      midt = (start + slut) / 2;
    }
    
    return -1;
  }

  ...
}
O( log n ) start og slut vil i ovenstående kode hele tiden nærme sig hinanden med aftagende hastighed. Man kan vise at tidskompleksiteten for binær søgning er O( log n ), og den er derfor betydelig bedre end den lineære søgning.