Wikimore

Summary

Example comparing two search algorithms. To look for "Morin, Arthur" in some ficitious participant list, linear search needs 28 checks, while binary search needs 5.

Svg version: File:Binary search vs Linear search example svg.svg.

LaTeX source code

\documentclass[12pt]{article}
\setlength{\unitlength}{1mm}
\usepackage{latin1}
\usepackage[pdftex]{color}
\usepackage[paperwidth=90\unitlength,paperheight=209\unitlength]{geometry}
\setlength{\topmargin}{-36mm}
\setlength{\textwidth}{90\unitlength}
\setlength{\textheight}{209\unitlength}
\setlength{\oddsidemargin}{-23mm}
\setlength{\parindent}{0cm}
\pagestyle{empty}
\begin{document}
\definecolor{fLin}      {rgb}{0.50,0.00,0.50}%  foreground: linear search
\definecolor{fBin}      {rgb}{0.00,0.50,0.50}%  foreground: binary search
\definecolor{bFnd}      {rgb}{0.80,0.99,0.30}%  background: found
\definecolor{bLst}      {rgb}{0.90,0.90,0.90}%  background: name list
\definecolor{bHd}       {rgb}{0.70,0.70,0.70}%  background: list header
\newcounter{nameHeight}
\newcounter{nextHeight}
\setcounter{nameHeight}{195}
\setcounter{nextHeight}{192}
\newcommand{\name}[1]{%
        \put(41,\arabic{nameHeight}){\makebox(0,0)[l]{%
                %\arabic{nameRank}
                \Large\sf #1}}%
        \addtocounter{nameHeight}{-6}%
        %\addtocounter{nameRank}{1}%
}
\newcommand{\next}{%
        \put(35,\arabic{nextHeight}){%
                \textcolor{fLin}{\put(4,3){\makebox(0,0)[r]{\tiny no}}}%
                \textcolor{fLin}{\put(0,0){\oval(8,4)[l]}}%
                \textcolor{fLin}{\put(-2,-2){\vector(1,0){2}}}%
        }%
        \addtocounter{nextHeight}{-6}%
}
\renewcommand{\,}{\raisebox{1mm}{,}}
\begin{picture}(85,204)%
\textcolor{bHd}{\put(40,198){\makebox(0,0)[bl]{\rule{45mm}{6mm}}}}%
\textcolor{bLst}{\put(40,0){\makebox(0,0)[bl]{\rule{45mm}{198mm}}}}%
\put(41,201){\makebox(0,0)[l]{\Large\bf Participants:}}%
\name{Abraham\, Max}%           
\name{Abt\, Antal}%             
\name{Barlow\, Peter}%          
\name{Bartoniek\, Géza}%        
\name{Barus\, Carl}%            
\name{Bauer\, Edmond}%          
\name{Beetz\, Johan}%           
\name{Belar\, Albin}%           
\name{Blondel\, André}%         
\name{Brewster\, David}%        
\name{Brillouin\, Léon}%        
\name{Dalén\, Gustaf}%          
\name{Dolbear\, Amos}%          
\name{Duhem\, Pierre}%          
\name{Eötvös\, Loránd}%         
\name{Fröhlich\, Pál}%          
\name{Graetz\, Leo}%            
\name{Hall\, Edwin}%            
\name{Holten\, Carl}%           
\name{Khvolson\, Orest}%        
\name{Knudsen\, Martin}%        
\name{Küch\, Richard}%          
\name{Lamb\, Horace}%           
\name{Lebedev\, Peter}%         
\name{Lehmann\, Otto}%          
\name{Lemoine\, Jules}%         
\name{Marsden\, Ernest}%        
\name{Morin\, Arthur}%          
\name{Perrin\, Jean}%           
\name{Poni\, Petru}%            
\name{Soret\, Charles}%         
\name{Weiss\, Pierre}%          
\name{Zeeman\, Pieter}%         
\thicklines%
\textcolor{fLin}{\put(15,200){\makebox(0,0)[l]{\tiny Linear}}}%
\textcolor{fLin}{\put(15,198){\makebox(0,0)[l]{\tiny Search}}}%
\textcolor{fLin}{\put(15,196){\vector(1,0){20}}}%
\next\next\next\next\next\next\next\next\next\next%     10
\next\next\next\next\next\next\next\next\next\next%     20
\next\next\next\next\next\next\next%
\textcolor{bFnd}{\put(39,34){\makebox(0,0)[r]{\rule{4mm}{3mm}}}}%
\textcolor{fLin}{\put(39,34){\makebox(0,0)[r]{\tiny yes}}}%
\textcolor{fBin}{\put(0.000,104.000){\makebox(0.000,0.000)[l]{\tiny Binary}}}%
\textcolor{fBin}{\put(0.000,102.000){\makebox(0.000,0.000)[l]{\tiny Search}}}%
\textcolor{fBin}{\put(0.000,100.000){\vector(1,0){20.000}}}%            A
\textcolor{fBin}{\put(26.000,100.000){\makebox(0.000,0.000)[r]{\tiny too}}}%
\textcolor{fBin}{\put(26.000,98.000){\makebox(0.000,0.000)[r]{\tiny high}}}%
\textcolor{fBin}{\put(18.000,52.000){\vector(1,0){2.000}}}%                     B
\textcolor{fBin}{\put(26.000,52.000){\makebox(0.000,0.000)[r]{\tiny too}}}%
\textcolor{fBin}{\put(26.000,50.000){\makebox(0.000,0.000)[r]{\tiny high}}}%
\textcolor{fBin}{\put(18.000,26.000){\vector(1,0){2.000}}}%                     C
\textcolor{fBin}{\put(26.000,28.000){\makebox(0.000,0.000)[r]{\tiny too}}}%
\textcolor{fBin}{\put(26.000,26.000){\makebox(0.000,0.000)[r]{\tiny low}}}%
\textcolor{fBin}{\put(18.000,40.000){\vector(1,0){2.000}}}%                     D
\textcolor{fBin}{\put(26.000,40.000){\makebox(0.000,0.000)[r]{\tiny too}}}%
\textcolor{fBin}{\put(26.000,38.000){\makebox(0.000,0.000)[r]{\tiny high}}}%
\textcolor{fBin}{\put(18.000,34.000){\vector(1,0){2.000}}}%                     E
\textcolor{bFnd}{\put(26.000,34.000){\makebox(0.000,0.000)[r]{\rule{4mm}{3mm}}}}%
\textcolor{fBin}{\put(26.000,34.000){\makebox(0.000,0.000)[r]{\tiny yes}}}%
\textcolor{fBin}{\put(20.000,75.000){\oval(29.000,46.000)[l]}}%                 A-->B
\textcolor{fBin}{\put(20.000,38.000){\oval(22.000,24.000)[l]}}%                 B-->C
\textcolor{fBin}{\put(20.000,34.000){\oval(15.000,12.000)[l]}}%                 C-->D
\textcolor{fBin}{\put(20.000,36.000){\oval(8.000,4.000)[l]}}%                   D-->E
\textcolor{bHd}{\multiput(40.000,204.000)(0.000,-6.000){35}{\line(1,0){45.000}}}%
\end{picture}
\end{document}

Licensing

I, the copyright holder of this work, release this work into the public domain. This applies worldwide.
In some countries this may not be legally possible; if so:
I grant anyone the right to use this work for any purpose, without any conditions, unless such conditions are required by law.

Category:Self-published work#Binary%20search%20vs%20Linear%20search%20example.pdf Category:PD-self#Binary%20search%20vs%20Linear%20search%20example.pdf Category:Media missing infobox template Category:Files by User:Jochen Burghardt Category:Search algorithms Category:Analysis of algorithms Category:Images with LaTeX source code Category:English-language PDF files

Wikimore

File:Binary search vs Linear search example.pdf

Summary

Licensing