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. See program LinkedListDemo for an example. It may also be used as part of a hash search to handle collisions. (See later).

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-organising, for example by putting the last item to be searched to the front of the list.

program LinearSearchDemo;
  {$Apptype Console}
const
  UPPER_BOUND = 10;
  //Multiple winners of men's open singles title at Wimbledon
  WimMultiChamps : array[1 .. UPPER_BOUND ] of string = ('Laver', 'Newcombe', 'Connors',
                   'Borg', 'McEnroe', 'Becker', 'Edberg', 'Sampras', 'Federer', 'Nadal');
var
  Last, Count : integer;
  Found : Boolean;
  Name : string;
begin
  Count := 1;
  Found := false;
  write('Enter the name to be found using the correct case e.g. McEnroe. ');
  readln(Name);
  while (Count <= UPPER_BOUND) and (not Found) do
    begin
      if WimMultiChamps[Count] = Name then
        begin
          writeln(Name, ' is in position ', Count);
          Found := true;
        end
      else
         Count := Count + 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.

This program is suited to a Smart Pascal console application. The Smart Pascal Code follows the program in action.

Demonstration

If the output fails to show in your current browser, try another such as Chrome. Click the Input button to obtain the edit box. Press Enter to see the result of the search for the surname that you type.

LinearSearchDemo.html

Smart Pascal Code

unit Unit1;

interface

uses 
  System.Types, System.Lists, SmartCL.System, SmartCL.Scroll, SmartCL.Console,
  SmartCL.Components, SmartCL.Application, SmartCL.ConsoleApp;

type
  TApplication = class(TW3CustomConsoleApplication)
  private
          //Multiple winners of men's open singles title at Wimbledon
    const WimMultiChamps: array[1..10] of string = ['Laver', 'Newcombe', 'Connors', 'Borg', 'McEnroe',
                                                    'Becker', 'Edberg', 'Sampras', 'Federer', 'Nadal'];
    const UPPER_BOUND = 10;
  protected
    procedure PopulateConsole; override;
    procedure ProcessCommand(aCommand: string); override;
  end;

implementation

procedure TApplication.PopulateConsole;
begin
  Header.Width := 600;
  Header.Title.Caption := 'Linear Search';
  Header.NextButton.Caption := 'Search';
  Console.SetSize(600, 300);
  Console.WriteLn('Enter the name to be found using the correct case e.g. McEnroe.');
end;
 
procedure TApplication.ProcessCommand(aCommand: string);
begin
  var Count = 1;
  var Found = False;
  while (Count <= UPPER_BOUND) and (not Found) do
    begin
      if WimMultiChamps[Count] = aCommand then
        begin
          Console.writeln(aCommand + ' is in position ' + intToStr(Count) + '.');
          Found := true;
        end
      else
        inc(Count);
    end;
    if not Found then
      Console.writeln(aCommand + ' is not in the list.');
end;

end.
Programming - a skill for life!

Linear search, binary search, binary search tree and hash search