File:Binary search vs Linear search example.pdf
Original file (531 × 1,233 pixels, file size: 24 KB, MIME type: application/pdf)
Captions
Summary edit
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 edit
Public domainPublic domainfalsefalse |
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 (talk | contribs) | 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 (talk | contribs) | 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. |
You cannot overwrite this file.
File usage on Commons
The following 2 pages use this file:
File usage on other wikis
The following other wikis use this file:
- Usage on en.wikipedia.org
- Usage on www.wikidata.org
Metadata
This file contains additional information such as Exif metadata which may have been added by the digital camera, scanner, or software program used to create or digitize it. If the file has been modified from its original state, some details such as the timestamp may not fully reflect those of the original file. The timestamp is only as accurate as the clock in the camera, and it may be completely wrong.
Software used | TeX |
---|---|
Conversion program | pdfTeX-1.40.3 |
Encrypted | no |
Page size | 255.117 x 592.438 pts |
Version of PDF format | 1.4 |