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 ggr...@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.