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.