# 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.

See below a simple demonstration as both Lazarus Smart Pascal console applications.

```program LinearSearchDemo;
{\$Apptype Console}
const
UPPER_BOUND = 11;
// 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', 'Murray');
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. ');
begin
if WimMultiChamps[Count] = Name then
begin
writeln(Name, ' is in position ', Count);
Found := true;
end
else
Count := Count + 1;
end;
begin
writeln(Name, ' is not in the list.');
end;
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.

## 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.

## 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..11] of string = ['Laver', 'Newcombe', 'Connors', 'Borg',
'McEnroe', 'Becker', 'Edberg', 'Sampras',
const UPPER_BOUND = 11;
protected
procedure PopulateConsole; override;
procedure ProcessCommand(aCommand: string); override;
end;

implementation

procedure TApplication.PopulateConsole;
begin
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;
begin
if WimMultiChamps[Count] = aCommand then
begin
Console.writeln(aCommand + ' is in position ' + intToStr(Count) + '.');
Found := true;
end
else
inc(Count);
end;