Binærsøk i tabell

Binærsøk er en veldig effektiv måte å søke i tabeller på. En forutsetning for at man skal kunne bruke binærsøk er at tabellen er sortert på forhånd

Måten dette skjer på er som følger:

• Går til midten av tabellen. Er den høyere eller lavere enn denne verdier, går man enten opp eller ned.
• Deretter deler man denne delen i 2 igjen. Er den høyere eller lavere, går man enten opp eller ned.
• Slik fortsetter man til man har funnet verdien. Da returnerer vi indeksen til denne plassen.
• Denne måten å søke på er utrolig mye raskere enn å søke igjennom hvert eneste element i tabellen.

#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>

const int str = 10;
int tabell[str]={0,1,2,3,5,6,7,8,9};

int binarSoek(int SortertTabell[], int forste, int siste, int finn) {
   while (forste <= siste) {
       int midt = (forste + siste) / 2;
       if (finn > SortertTabell[midt])
           forste = midt + 1;
       else if (finn < SortertTabell[midt])
           siste = midt - 1;
       else
           return midt;
   }
   return -(forste + 1);
}

int main()
{
	cout<<binarSoek(tabell,0,9,7);
	return 0;
}