[Back to TUTOR SWAG index] [Back to Main SWAG index] [Original]

                           Turbo Pascal for DOS Tutorial
                                by Glenn Grotzinger
                          Part 16: Searching an Array
                    copyright(c) 1995-96 by Glenn Grotzinger

    There was no defined problem in part 15, so we will start.

    Sequential Array Search
    =======================
    This method for searching arrays for items is much like the bubblesort
    is for sorting arrays.  It works well for small arrays, but for larger
    arrays, it is very inefficient, if we are merely interested in the
    existence of an item in the array.  Basically, it's a very simple
    proposition to set up a sequential array search.

    program example_of_sequential_search;

      var
        a: array[1..15] of integer;
        i, number: integer;
        found: boolean;

      begin
        randomize;
        found := false;

        write('The array is: ');
        for i := 1 to 15 do
          begin
            a[i] := random(10) + 1;
            write(a[i], ' ');
          end;
        writeln;

        writeln('Enter a number, and we shall see if it is in the array');
        readln(number);

        i := 1;
        while i <= 15 do
          begin
            if a[i] = number then
              begin
                writeln(number, ' was found at position ', i);
                { i := 15; can be done to break the loop on the first
                  encounter of the one if we are interested in just
                  whether the number exists in the array }
                found := true;
              end;
            inc(i);
          end;
        if not found then
          writeln(number, ' was not found in the array.');
      end.

    Binary Search
    =============
    The other type of algorithm we will discuss is the binary search.  It is
    to searching an array what the quicksort is to sorting an array.  Basically,
    what it will do is keep halfing the array...

    This method of array search has a prerequisite of having the data sorted.
    Basically, we probably would want to sort data anyway to make it in
    a readily presentable format for the user, so this doesn't necessarily
    matter  (searches and sorts are products of data processing programs
    normally, anyway).

    program example_of_binary_search;

      const
        first = 1;
        last = 15;
      var
        a: array[first..last] of integer;
        i, number: integer;
        found: boolean;
        location: integer;

      procedure bsearch(var number, location: integer;
                          lowend, highend: integer; var found: boolean);
        var
          midpoint: integer;
        begin
          if lowend > highend then
            found := false
          else
            begin
              midpoint := (lowend + highend) div 2;
              if number = a[midpoint] then
                begin
                  found := true;
                  location := midpoint;
                end
              else if number < a[midpoint] then
                bsearch(number, location, lowend, midpoint-1, found)
              else if number > a[midpoint] then
                bsearch(number, location, midpoint+1, highend, found);
            end;
        end;

      begin
        randomize;
        found := false;

        write('The array is: ');
        for i := 1 to 15 do
          begin
            { to insure we have sorted data }
            a[i] := 3*i;
            write(a[i], ' ');
          end;
        writeln;

        writeln('Enter a number, and we shall see if it is in the array');
        readln(number);

        bsearch(number, location, first, last, found);

        if found then
          writeln(number, ' was found at position ', location)
        else
          writeln(number, ' was not found. ');

    end.

    As you may be able to pick out of this, it is possible to write an iterative
    version of the bsearch procedure.  With sorting the array, though, this one
    is a little better than simply going through the array one by one, but it
    still has it's drawback of having to actually sort the information.

    Another method available for use, which we will not discuss here is called
    hashing, which is a very complex matter.

    What should you use?  The serial search I described originally could be
    very good, for a limited number of searches on a small array size.

    If it's not good to do the serial search, and you needed to sort the data
    anyway, the binary search is best.

    Another method you may see as possible to use will be covered later, called
    the binary search tree.  The cost in that approach will be basically building
    the tree initially, then traversing it.  The tree is built based on specific
    rules, which we can exploit to cause a search.

    Practice Programming Problem #16
    ================================
    Randomly generate 1000 numbers from 1-10000 into an array.
    Then generate another 500 numbers from 1-10000.
    If there is a number from the second set of numbers that happens
    to be in the first set of numbers, write out to the file named
    LOCATION.TXT something such as:

    5322 was found in position 532.

    Only indicate the first instance of the number you encounter.

    Next Time
    =========
    We will cover some basic concepts of the use of pointers.  Please
    write any comments you have to ggrotz@2sprint.net.  As I look at
    my formatted version, so far there has been 116 pages written of
    this tutorial, from part 1, not counting this one.  As I look through
    my line count figures, this one is the smallest. (interesting facts,
    huh?)

    I will ask for feedback on how I do with regards to any of the pointer
    related texts coming up.  Please do that.  Thank you.

[Back to TUTOR SWAG index] [Back to Main SWAG index] [Original]