Implementeer binair zoeken om een getal terug te vinden in een gesorteerde lijst, zoals in de vorige leesactiviteit.

Opgave

Je krijgt een beginbestand waarin het meeste al voor je geschreven is:

• een grote, oplopend gesorteerde lijst lijst met gehele getallen;
• de in- en uitvoer: het programma leest het gezochte getal van de invoer, roept de functie IndexInLijst op, en drukt het resultaat af.

Jij hoeft enkel de functie IndexInLijst in te vullen:

int IndexInLijst(int[] getallen, int getal)
{
    // TODO: implementeer hier binair zoeken
    return -1;
}

De functie krijgt de gesorteerde lijst getallen en het gezochte getal. Ze geeft de nul-gebaseerde index terug van getal in getallen (het eerste element heeft index 0), of -1 als het getal niet in de lijst zit. Zoek met binair zoeken (verdeel en heers), dus niet met een gewone lus die elk element één voor één overloopt.

Gebruik de aanpak uit de leesactiviteit: hou twee grenzen links en rechts bij, bereken telkens het midden met een gehele deling, en gooi de helft weg waarin het getal niet kan zitten. Vergeet de + 1 bij links = midden + 1 niet, anders riskeer je een oneindige lus.

Invoer

Eén regel met het gezochte getal.

Uitvoer

Eén regel: staat het getal in de lijst, dan <getal> staat op index <index> (met <index> de nul-gebaseerde positie); zit het er niet in, dan <getal> zit niet in de lijst.

Voorbeelden

Het getal 516 staat in de lijst, op positie 100:

Invoer:

516

Uitvoer:

516 staat op index 100

Het getal 500 zit niet in de lijst:

Invoer:

500

Uitvoer:

500 zit niet in de lijst