13.1. SEARCHING 227
couldbeanywhereinthelist,sowestartwithvariableslowandhighsettothefirstandlastpositionsof
thelist,respectively.
Theheartofthealgorithmis a loopthatlooksat theitemin themiddleoftheremainingrangeto compare
it tox. Ifxis smallerthanthemiddleitem,thenwemovetop, sothatthesearchis narrowedtothelower
half.Ifxis larger, thenwemovelow, andthesearchis narrowedtotheupperhalf.Theloopterminates
whenxis foundortherearenolongerany moreplacestolook(i.e.,low > high). Hereis thecode.
def search(x, nums):
low = 0
high = len(nums)- 1
while low <= high: # There is still a range to search
mid = (low+ high) / 2 # position of middle item
item = nums[mid]
if x == item: # Found it! Return the index
return mid
elif x < item: # x is in lower half of range
high = mid - 1 # move top marker down
else: # x is in upper half
low = mid + 1 # move bottom marker up
return -1 # no range left to search, x is not there
Thisalgorithmis quitea bitmoresophisticatedthanthesimplelinearsearch.Youmightwanttotrace
througha coupleofexamplesearchestoconvinceyourselfthatit actuallyworks.
13.1.4 ComparingAlgorithms.
Sofar, wehave developedtwo solutionstooursimplesearchingproblem.Whichoneis better?Well,that
dependsonwhatexactlywemeanbybetter. Thelinearsearchalgorithmis mucheasiertounderstandand
implement.Ontheotherhand,weexpectthatthebinaryseachis moreefficient,becauseit doesn’t have to
lookateveryvalueinthelist.Intuitively, then,wemightexpectthelinearsearchtobea betterchoicefor
smalllistsandbinarysearcha betterchoiceforlargerlists.How couldweactuallyconfirmsuchintuitions?
Oneapproachwouldbetodoanempiricaltest.We couldsimplycodeupbothalgorithmsandtrythem
outonvarioussizedliststoseehowlongthesearchtakes. Thesealgorithmsarebothquiteshort,soit
wouldnotbedifficulttoruna few experiments.WhenI testedthealgorithmsonmyparticularcomputer(a
somewhatdatedlaptop),linearsearchwasfasterforlistsoflength 10 orless,andtherewasnosignificant
differenceintherangeoflength10–1000.Afterthat,binarysearchwasa clearwinner. Fora listofa million
elements,linearsearchaveraged2.5secondstofinda randomvalue,whereasbinarysearchaveragedonly
0.0003seconds.
Theempiricalanalysishasconfirmedourintuition,buttheseareresultsfromoneparticularmachine
underspecificcircumstances(amountofmemory, processorspeed,currentload,etc.).How canwebesure
thattheresultswillalwaysbethesame?
Anotherapproachis to analyzeouralgorithmsabstractlyto seehow efficientthey are.Otherfactorsbeing
equal,weexpectthealgorithmwiththefewestnumberof“steps”tobethemoreefficient.Buthowdowe
countthenumberofsteps?Forexample,thenumberoftimesthateitheralgorithmgoesthroughitsmainloop
willdependontheparticularinputs.We have alreadyguessedthattheadvantageofbinarysearchincreases
asthesizeofthelistincreases.
Computerscientistsattacktheseproblemsbyanalyzingthenumberofstepsthatanalgorithmwilltake
relative tothesizeordifficultyofthespecificprobleminstancebeingsolved.Forsearching,thedifficultyis
determinedbythesizeofthecollection.Obviously, it takesmorestepstofinda numberina collectionofa
millionthanit doesina collectionoften.Thepertinentquestionishowmanystepsare neededtofinda value
ina listofsizen. We areparticularlyinterestedinwhathappensasngetsverylarge.
Let’s considerthelinearsearchfirst.If wehave a listoftenitems,themostworkouralgorithmmight
have todois tolookat eachiteminturn.Theloopwilliterateat mosttentimes.Supposethelistis twiceas
big.Thenwemighthave tolookattwiceasmany items.If thelistis threetimesaslarge,it willtake three