[PASCAL] Linear / Sequential Search

[CouldnoT]

Linear / Sequential Search

 

 

 

A linear search operates by comparing the search value with each item in the list sequentially until the target is found or until the last item has been processed. For ordered lists, the average performance can be improved by giving up at the first item which is greater than the unmatched target.

 

A linear search is appropriate for linked lists. It may also be used as part of a hash search to handle collisions. 

 

The performance of a linked list depends on the arrangement of the items in the list. Clearly it is an advantage to have the most frequently accessed items at the front of the list. The list can be self-organizing, for example by putting the last item to be searched to the front of the list

 

See below a simple demonstration :

 

program LinearSearch;

const
  start = 11;
  // Multiple winners of men's open singles title
  ArrayOfString : array[1 .. UPPER_BOUND ] of string = ('Messi', 'Ronaldo', 'Anna',
                   'Maria', 'Salah', 'shakespeare', 'Fernando', 'CouldnoT', 'Mariem', 'Mohamed', 'Mario');
var
  Last, i : integer;
  Found : Boolean;
  Name : string;
begin
  i := 1;
  Found := false;
  write('Enter the name to be searched for: '); readln(Name);
  
  while (i <= start) and (not Found) do
    begin
      if ArrayOfString[i] = Name then
        begin
          writeln(Name, ' is in position ', i);
          Found := true;
        end
      else
         i := i + 1;
    end;

    if not Found then
      begin
        writeln(Name, ' is not in the list.');
      end;
    readln;
end.

 

Here the array is not sorted alphabetically and all the items must be compared with the search string if it is not in the list. The Smart Pascal code follows the program in action.

Edited August 17, 2020 by CouldnoT

[CouldnoT]

Edited October 21, 2020 by CouldnoT