226 CHAPTER13. ALGORITHMANALYSISANDDESIGN
nums = [3,1,4,2,5]
nums.index(4)
2
Infact,theonlydifferencebetweenoursearchfunctionandindexis thatthelatterraisesanexceptionif
thetargetvaluedoesnotappearinthelist.We couldimplementthesearchfunctionusingindexbysimply
catchingtheexceptionandreturning-1forthatcase.
def search(x, nums):
try:
return nums.index(x)
except:
return -1
Thisapproachbegsthequestion,however. Therealissueis how doesPythonactuallysearchthelist?What
is thealgorithm?
13.1.2 Strategy1:LinearSearch.
Let’s tryourhandat developinga searchalgorithmusinga simple“bethecomputer”strategy. Supposethat
I gave youa pagefullofnumbersinnoparticularorderandaskedwhetherthenumber 13 is inthelist.How
wouldyousolve thisproblem?If youarelike mostpeople,youwouldsimplyscandownthelistcomparing
eachvalueto13.Whenyousee 13 inthelist,youquitandtellmethatyoufoundit.If yougettothevery
endofthelistwithoutseeing13,thenyoutellmeit’s notthere.
Thisstrategyis calledalinearsearch. Youaresearchingthroughthelistofitemsonebyoneuntilthe
targetvalueis found.Thisalgorithmtranslatesdirectlyintosimplecode.
def search(x, nums):
for i in range(len(nums)):
if nums[i]== x: # item found, return the indexvalue
return i
return -1 # loop finished, item was not in list
Thisalgorithmwasnothardtodevelop,andit willworkverynicelyformodest-sizedlists. Foran
unorderedlist,thisalgorithmis asgoodasany. ThePythoninandindexoperatorsbothimplementlinear
searchingalgorithms.
If wehave a verylargecollectionofdata,wemightwanttoorganizeit insomewaysothatwedon’t have
tolookat everysingleitemtodeterminewhere,orif,a particularvalueappearsinthelist.Supposethatthe
listis storedinsortedorder(lowesttohighest).Assoonasweencountera valuethatis greaterthanthetarget
value,wecanquitthelinearsearchwithoutlookingat therestofthelist.Onaverage,thatsavesusabouthalf
ofthework.But,if thelistis sorted,wecandoevenbetterthanthis.
13.1.3 Strategy2:BinarySearch
Whena listis ordered,thereis a muchbettersearchingstrategy, onethatyouprobablyalreadyknow. Have
youeverplayedthenumberguessinggame?I picka numberbetween1 and100,andyoutrytoguesswhat
it is.Eachtimeyouguess,I willtellyouif yourguessis correct,toohigh,ortoolow. Whatis yourstategy?
Ifyouplaythisgamewitha veryyoungchild,they mightwelladopta strategyofsimplyguessing
numbersatrandom. Anolderchildmightemploy a systematicapproachcorrespondingtolinearsearch,
guessing 1 2 3 4 untilthemysteryvalueis found.
Ofcourse,virtuallyany adultwillfirstguess50. Iftoldthatthenumberishigher, thentherangeof
possiblevaluesis 50–100. Thenextlogicalguessis 75. Eachtimeweguessthemiddleoftheremaining
rangetotrytonarrow downthepossiblerange.Thisstrategyis calledabinarysearch. Binarymeanstwo,
andat eachstep,wearedividingthepossiblerangeintotwo parts.
We canemploy a binarysearchstrategytolookthrougha sortedlist.Thebasicideais thatweusetwo
variablestokeeptrackoftheendpointsoftherangeinthelistwheretheitemcouldbe.Initially, thetarget