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
    writeln('Not found.');
end;

begin
  writeln('Enter the number to search for e.g. 154, 170 or 275');
  readln(Num);
  BinarySearch(Num);
  readln;
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');
  readln(Num);
  BinarySearch(Num, 1, UPPER_BOUND);
  readln;
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
  Header.Width := 550;
  Header.Title.Caption := 'Binary Search';
  Header.NextButton.Caption := 'Input';
  Header.NextButton.Left := Header.Width - Header.NextButton.Width;
  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.