# Binary Search

A binary search first compares the search item to an item at the middle of the list. If there is not a match, the code determines which half of the list to carry out the next search using the same method. This iterative or recursive process is repeated until the search item is found or it is shown to be absent.

We provide an iterative and then a recursive version of this important search method, followed by a Smart Pascal web demonstration and its code.

```program BinarySearchDemo1;
{\$Apptype Console}
const
UPPER_BOUND = 16;
Nums : array[1 .. UPPER_BOUND] of integer =  (61, 87, 154, 170, 275,
426, 503, 509, 512, 612, 653, 677, 703, 765, 897, 908);
var
Num : integer;

procedure BinarySearch(SearchNum : integer);
var
Found, Failed: Boolean;
Last, First, MidPoint: integer;
begin
Found := False;
Failed:= False;
Last := UPPER_BOUND;
First := 1;
repeat
Midpoint := (First + Last) DIV 2;
if Nums[MidPoint] = SearchNum then
begin
Found := True;
writeln('Found at position ' ,MidPoint);
end
else if (First > Last) then
Failed := true;
else if Nums[MidPoint] < SearchNum then
First := MidPoint + 1;
else
Last := MidPoint - 1;
until Found or Failed;
if Failed then
end;

begin
writeln('Enter the number to search for e.g. 154, 170 or 275');
BinarySearch(Num);
end.```

The following is a neater, recursive solution.

```program BinarySearchDemo2;
{\$Apptype Console}
const
UPPER_BOUND = 16;
Nums : array[1 .. UPPER_BOUND] of integer =  (61, 87, 154, 170, 275,
426, 503, 509, 512, 612, 653, 677, 703, 765, 897, 908);
var
Num : integer;

procedure BinarySearch(SearchNum, First, Last : integer);
var
MidPoint: integer;
begin
if First > Last then
writeln('Search Failed')
else
begin
writeln('Searching for ', SearchNum, ' between index ',First ,' and index ', Last);
Midpoint := (First + Last) DIV 2;
if Nums[MidPoint] = SearchNum then
writeln('Found at position ', MidPoint)
else if Nums[MidPoint] < SearchNum then
BinarySearch(SearchNum, MidPoint + 1, Last)
else
BinarySearch(SearchNum, First, MidPoint - 1);
end;
end;

begin
writeln('Enter the number to search for e.g. 154, 170, 275 or 897');
BinarySearch(Num, 1, UPPER_BOUND);
end.

```

## 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 integer 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
const UPPER_BOUND = 16;
const Nums: array[1 .. 16] of integer = [61, 87, 154, 170, 275, 426, 503, 509,
512, 612, 653, 677, 703, 765, 897, 908];

protected
procedure PopulateConsole; override;
procedure ProcessCommand(aCommand: string); override;
procedure BinarySearch(SearchNum, First, Last : integer);
end;

implementation

procedure TApplication.BinarySearch(SearchNum, First, Last : integer);
var
MidPoint: integer;
begin
if First > Last then
Console.writeln('Search Failed')
else
begin
Console.writeln('Searching for ' + intToStr(SearchNum) + ' between index ' +
intToStr(First) + ' and index ' + intToStr(Last));
Midpoint := (First + Last) DIV 2;
if Nums[MidPoint] = SearchNum then
Console.writeln('Found at position ' + intToStr(MidPoint))
else if Nums[MidPoint] < SearchNum then
BinarySearch(SearchNum, MidPoint + 1, Last)
else
BinarySearch(SearchNum, First, MidPoint - 1);
end;
end;

procedure TApplication.PopulateConsole;
begin
Console.SetSize(550, 300);
Console.WriteLn('Enter the number to search for e.g. 154, 170, 275 or 897');
end;

procedure TApplication.ProcessCommand(aCommand: string);
begin
BinarySearch(strToInt(aCommand), 1, UPPER_BOUND);
end;

end.

```
Programming - a skill for life!

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