With the phenomenal rise of the Internet searching has become a hot topic in computing. The techniques described here are not the same as those used by Google and other search engines but they are conceptually similar. The central issue is working through data in a systematic way to locate an item specified in advance.
One way to achieve this is a linear search, that is starting at the beginning of a data set and working through it item by item until the specified one is found. Another approach is the 'binary' search, where the data set is searched by starting at the mid-point of the data set and the subsequent search is then confined to either the lower or the upper half.
Given a set of data in an array this type of search is straightforward. The data might be in an array like these numbers:
numlist:array[1..10] of datatype;
23 12 54 36 76 14 98 15 83 11
To search for an item such as 98 we need this code:
for i := 1 to length(numlist) do
if numlist[i] = item_required then found:=true;
if found then showmessage('Item ' + item_required +' was found');
Instead of 'item_required' we might have the contents of, say, an edit box: edit1.text.
This approach examines the whole list regardless of where the item was found, in cell [1], for example. We can avoid examining every cell by using a while loop:
i:=1;
found := false;
while not (found) do
if item_required = numlist[i] then found:= true
else inc(i);
if found then showmessage('Item ' + numlist[i] +' was found');
This code sets a Boolean variable to false and then scans the list. If there is a match between the item specified and the current item in the array then the Boolean variable is set to true and the search ends; if there is no match then i is incremented and the search continues.
The problem with this code - well, can you see the problem? What if the item is not present? The while condition does not allow for this so an adjustment is required:
i:=1;
found := false;
while not (found) and (i <= length(numlist)) do
if item_required = numlist[i] then found:= true
else inc(i);
if found then showmessage('Item ' + item_required +' was found');
The loop will now finish when i is 10, or whatever the length of numlist. We might also amend the last line to provide a message if the item is not found:
if found then showmessage ('Item ' +
strtoint(edit1.text) +' was found')
else showmessage ('Item ' + strtoint(edit1.text) + ' was not found';
Instead of showmessage we might use an edit box or a caption:
if found then edit2.text := 'Item ' +
strtoint(edit1.text) +' was found'
else edit2.text := 'Item ' + strtoint(edit1.text) +' was not found'
or
if found then label3.caption := 'Item ' +
strtoint(edit1.text) +' was found'
else label3.caption := 'Item ' + strtoint(edit1.text) +' was not found'
These strategies will work with any array of data items, including record types:
if name_required = name_list[i].name then...
Files, specifically sequential files, are also searched in a linear fashion:
found := false;
while not eof (datafile) do
begin
read (datafile, datarecord);
if name_required = datarecord.name then
begin
found := true;
data_required:=datarecord.data;
end;
if found then eof(datafile):=true;
end;
The average number of searches needed to find an item in a linear search is given by the simple formula number_of_items/2. It doesn't matter whether a list is sorted or not, this will not change the likelihood of the next item in the search being the one you want.
Imagine searching a telephone directory for numbers where each time you started at the beginning and read the names until you found the one you wanted. This would be very tedious because, on average, it would take you the number of names divided by 2 times to find the number required. Telephone directories provide another technique to help you search for names and numbers, namely the index, but that is another story.