Chapter 13
Algorithm Analysis and Design
Ifyouhave workedyourwaythroughtothispointinthebook,youarewellonthewaytobecominga
programmer. WaybackinChapter1,I discussedtherelationshipbetweenprogrammingandthestudyof
computerscience. Nowthatyouhave someprogrammingskills,youarereadytostartconsideringthe
broaderissuesinthefield.Herewewilltake uponeofthecentralissues,namelythedesignandanalysisof
algorithms.
13.1 Searching
Let’s beginbyconsideringa verycommonandwell-studiedprogrammingproblem:search. Searchis the
processoflookingfora particularvalueina collection.Forexample,a programthatmaintainsthemember-
shiplistfora clubmightneedto lookuptheinformationabouta particularmember. Thisinvolvessomeform
ofsearchprocess.
13.1.1 A SimpleSearchingProblem.
To make thediscussionofsearchingalgorithmsassimpleaspossible,let’s boiltheproblemdowntoits
essentialessence.Hereis thespecificationofa simplesearchingfunction:
def search(x, nums):
nums is a listof numbers and x is a number
RETURNS the positionin the list where x occurs or -1 if
x is not in the list.
Herearea coupleinteractive examplesthatillustrateitsbehavior:
search(4, [3, 1, 4, 2, 5])
2
search(7, [3, 1, 4, 2, 5])
-1
Inthefirstexample,thefunctionreturnstheindex where 4 appearsinthelist.Inthesecondexample,the
returnvalue-1indicatesthat 7 is notinthelist.
YoumayrecallfromourdiscussionoflistoperationsthatPythonactuallyprovidesa numberofbuilt-in
search-relatedmethods.Forexample,wecantesttoseeif a valueappearsina sequenceusingin.
if x in nums:
do something
If wewanttoknow thepositionofxina list,theindexmethodfillsthebillnicely.