File:Binary search vs Linear search example.pdf
Size of this JPG preview of this PDF file: 258 × 599 pixels. Other resolutions: 103 × 240 pixels | 531 × 1,233 pixels.
Original file (531 × 1,233 pixels, file size: 24 KB, MIME type: application/pdf)
 | This is a file from the Wikimedia Commons. Information from its description page there is shown below. Commons is a freely licensed media file repository. You can help. |
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. |
File history
Click on a date/time to view the file as it appeared at that time.
| Date/Time | Thumbnail | Dimensions | User | Comment | |
|---|---|---|---|---|---|
| current | 12:50, 14 May 2017 |  | 531 × 1,233 (24 KB) | Jochen Burghardt | less extreme aspect ratio; changed colors to avoid interference with wikilink colors; made each binary-search jump length a power of 2 |
| 12:23, 12 April 2017 |  | 531 × 1,564 (25 KB) | Jochen Burghardt | Example comparing two search algorithms. To look for "Lobo, Haddock" in some ficitious participant list, linear search needs 34 checks, while binary search needs 5. |
File usage
The following page uses this file:
Global file usage
The following other wikis use this file:
- Usage on www.wikidata.org