11.5 Niet-lineair zoeken

Vijftig staten vormen de Verenigde Staten van Amerika. Elke staat heeft een naam en een afkorting van twee letters. AK is Alaska, AL is Alabama, AR is Arkansas, AZ is Arizona, CA is California enzovoort. Deze afkortingen en namen kunnen we opslaan in een tabel. Daarbij zorgen we voor een alfabetische volgorde van de afkortingen. In COBOL kunnen we die tabel als volgt beschrijven:

01 Verenigde-Staten.
   03 Staat           occurs 50 times
                      ascending key is Afkorting
                      indexed by VS-index.
      05 Afkorting    pic XX.
      05 Staatnaam    pic X(14).
  

Nieuw in deze beschrijving is ascending key. Deze vermelding vertelt de computer dat de waarden van de verschillende velden Afkorting in oplopende (Engels: ascending) volgorde in de tabel zijn opgenomen. Als de afkortingen in dalende volgorde zouden zijn opgenomen, dan hadden we vermeld: descending key is Afkorting. Om een niet-lineaire zoekmethode te kunnen toepassen moet de tabel of een deel van de tabel in volgorde liggen. Daarvoor moeten we zelf zorgen. De vermelding ascending key of descending key zorgt daar niet voor. Die is alleen bedoeld om de computer te vertellen welk veld hij bij de zoekmethode kan gebruiken.

illustratie: Geert Nijmolen

De opdracht voor niet-lineair zoeken is in COBOL search all. Hij is bedoeld om uit een gesorteerde reeks één element op te zoeken. Er is niet voorgeschreven welke methode de compiler-bouwer moet gebruiken; alleen dat die methode niet lineair mag zijn. We kunnen veilig aannemen dat alle fabrikanten kiezen voor de halveringsmethode. Dat is de snelste zoekmethode. Als we op een snelle manier een ingevoerde afkorting willen opzoeken, dan coderen we:

display "Welke tweelettercode?" with no advancing
accept invoer-afkorting
search all Staat 
   at end display "Dat is geen afkorting voor een staat."
   when Afkorting(VS-index) = invoer-afkorting
        display "Dit is de afkorting van ", 
            Staatnaam(VS-index)
end-search
  

Na de invoer van een tweecijferige afkorting komt de opdracht search all. De computer zoekt in de tabel naar de overeenkomstige afkorting. Is die er, dan wordt de bijbehorende naam van de staat zichtbaar. Is de afkorting niet aanwezig, dan komt het gedeelte na at end aan bod.

onthoud

Het veld na search all moet beschreven zijn met indexed by en met een ascending key of descending key. 

De conditie na when mag niet zomaar elke voorwaarde zijn. In de eerste plaats is alleen een test op gelijkheid mogelijk. Bovendien moet aan de linkerkant van het is-gelijk-teken een veld staan dat genoemd is als ascending key of descending key. Zoals uit de formaatbeschrijving (zie aanhangsel A2) blijkt, mag de voorwaarde worden verscherpt via and. Voor de tweede en volgende voorwaarden gelden dezelfde restricties als voor de eerste.

Bij de opdracht search all gebruikt de computer de gehele tabel. Om het zoekproces correct te laten verlopen, moeten we zorgen dat de tabel geheel gevuld is. Een andere mogelijkheid biedt het gebruik van occurs met depending on. We maken de tabel dan niet groter dan nodig is en kunnen search all zonder problemen gebruiken.