228 CHAPTER13. ALGORITHMANALYSISANDDESIGN
timesaslong,etc.Ingeneral,theamountoftimerequiredis linearlyrelatedtothesizeofthelistn. Thisis
whatcomputerscientistscallalineartimealgorithm.Now youreallyknow whyit’s calleda linearsearch.
Whataboutthebinarysearch?Let’s startbyconsideringa concreteexample.Supposethelistcontains
sixteenitems.Eachtimethroughtheloop,theremainingrangeis cutinhalf.Afteronepass,thereareeight
itemslefttoconsider. Thenexttimethroughtherewillbefour, thentwo,andfinallyone.How many times
willtheloopexecute?It dependsonhow many timeswecanhalve therangebeforerunningoutofdata.This
tablemighthelpyoutosortthingsout:
Listsize Halvings
1 0
2 1
4 2
8 3
16 4
Canyouseethepatternhere?Eachextraiterationoftheloopdoublesthesizeofthelist.If thebinary
searchloopsitimes,it canfinda singlevalueina listofsize 2 i. Eachtimethroughtheloop,it looksat
onevalue(themiddle)inthelist.To seehow many itemsareexaminedina listofsizen, weneedtosolve
thisrelationship:n 2 ifori. Inthisformula,iis justanexponentwitha baseof2.Usingtheappropriate
logarithmgivesusthisrelationship:i log 2 n. Ifyouarenotentirelycomfortablewithlogarithms,just
rememberthatthisvalueis thenumberoftimesthata collectionofsizencanbecutinhalf.
OK,sowhatdoesthisbitofmathtellus? Binarysearchis anexampleofalog timealgorithm. The
amountoftimeit takestosolve a givenproblemgrowsasthelogoftheproblemsize.Inthecaseofbinary
search,eachadditionaliterationdoublesthesizeoftheproblemthatwecansolve.
Youmightnotappreciatejusthowefficientbinarysearchreallyis.Letmetrytoputit inperspective.
Supposeyouhave a New YorkCityphonebookwith,say, twelve millionnameslistedinalphabeticalorder.
Youwalkupto a typicalNew Yorker onthestreetandmake thefollowingproposition(assumingtheirnumber
is listed):I’mgoingtotryguessingyourname.EachtimeI guessa name,youtellmeif yournamecomes
alphabeticallybeforeorafterthenameI guess.How many guesseswillyouneed?
Ouranalysisabove showstheanswertothisquestionislog 212 000 000.If youdon’t have a calculator
handy, hereis a quickwaytoestimatetheresult. 210 1024 orroughly1000,and 1000 x 1000 1 000 000.
Thatmeansthat 210 x 210 220 1 000 000. Thatis, 220 isapproximatelyonemillion. So,searchinga
millionitemsrequiresonly 20 guesses. Continutingon,weneed 21 guessesfortwo million, 22 forfour
million, 23 foreightmillion,and 24 guessestosearchamongsixteenmillionnames.We canfigureoutthe
nameofa totalstrangerinNewYorkCityusingonly 24 guesses!Bycomparison,a linearsearchwould
require(onaverage)6 millionguesses.Binarysearchis a phenomenallygoodalgorithm!
I saidearlierthatPythonusesa linearsearchalgorithmtoimplementitsbuilt-insearchingmethods.If a
binarysearchis somuchbetter, whydoesn’t Pythonuseit?Thereasonis thatthebinarysearchis lessgeneral;
inordertowork,thelistmustbeinorder. If youwanttousebinarysearchonanunorderedlist,thefirstthing
youhave todois putit inorderorsortit. Thisis anotherwell-studiedproblemincomputerscience,and
onethatweshouldlookat.Beforeweturntosorting,however, weneedtogeneralizethealgorithmdesign
techniquethatweusedtodevelopthebinarysearch.
13.2 Recursive Problem-Solving.
Rememberthebasicideabehindthebinarysearchalgorithmwastosucessivelydividetheprobleminhalf.
Thisis sometimesreferredtoasa “divideandconquer”approachtoalgorithmdesign,andit oftenleadsto
veryefficientalgorithms.
Oneinterestingaspectofdivideandconqueralorithmsis thattheoriginalproblemdividesintosubprob-
lemsthatarejustsmallerversionsoftheoriginal.To seewhatI mean,thinkaboutthebinarysearchagain.
Initially, therangetosearchis theentirelist.Ourfirststepis tolookat themiddleiteminthelist.Shouldthe
middleitemturnouttobethetarget,thenwearefinished.If it is notthetarget,wecontinuebyperforming
binarysearch oneitherthetop-halforthebottomhalfofthelist.
Usingthisinsight,wemightexpressthebinarysearchalgorithminanotherway.