上海交通大学：《Computational Thinking and Approach》教学资源（课件讲稿）Lecture10 ALGORITHM DESIGN AND ANALYSIS To the Classic

上游充通大 ParisTech SHANGHAI JIAO TONG UNIVERSITY INSTITUT DES SCIENCES ET TECHNOLOGIES PARIS INSTITUTE OF TECHNOLOGY Computational Thinking and Approach Lecture 10 Dr.Jialiang LU Jialiang.lu@situ.edu.cn

Computational Thinking and Approach Lecture 10 Dr. Jialiang LU Jialiang.lu@sjtu.edu.cn 1

上海充通大 ParisTech SHANGHAI JIAO TONG UNIVERSITY INSTITUT DES SCIENCES ET TECHNOLOGIES PARIS INSTITUTE OF TECHNOLOGY To the Classic ALGORITHM DESIGN AND ANALYSIS 2

ALGORITHM DESIGN AND ANALYSIS To the Classic 2

上游充通大 ParisTech SHANGHAI JIAO TONG UNIVERSITY INSTITUT DES SCIENCES ET TECHNOLOGIES PARIS INSTITUTE OF TECHNOLOGY Outines 。Searching Recursive Problem-Solving ·Sorting Algorithms 。Hard Problems 3

Outlines • Searching • Recursive Problem-Solving • Sorting Algorithms • Hard Problems 3

上游充通大 ParisTech SHANGHAI JIAO TONG UNIVERSITY INSTITUT DES SCIENCES ET TECHNOLOGIES PARIS INSTITUTE OF TECHNOLOGY Searching Searching is the process of looking for a particular value in a collection. o For example,a program that maintains student records might need to look up GPA for a particular student-this involves some sort of search process. 4

4 Searching • Searching is the process of looking for a particular value in a collection. • For example, a program that maintains student records might need to look up GPA for a particular student – this involves some sort of search process

上游充通大 ParisTech SHANGHAI JIAO TONG UNIVERSITY INSTITUT DES SCIENCES ET TECHNOLOGIES PARIS INSTITUTE OF TECHNOLOGY A simple Searching Problem Here is the specification of a simple searching function: def search(x,nums): nums is a list of numbers and x is a number Returns the position in the list where x occurs or -1 if x is not in the list. Here are some sample interactions: >>>search(4,[3,1,4,2,5]) 2 >>>search(7,[3,1,4,2,5]) -1 Python Programming,2/e 5

Python Programming, 2/e 5 A simple Searching Problem • Here is the specification of a simple searching function: def search(x, nums): # nums is a list of numbers and x is a number # Returns the position in the list where x occurs # or -1 if x is not in the list. • Here are some sample interactions: >>> search(4, [3, 1, 4, 2, 5]) 2 >>> search(7, [3, 1, 4, 2, 5]) -1

上降充通大 ParisTech SHANGHAI JIAO TONG UNIVERSITY INSTITUT DES SCIENCES ET TECHNOLOGIES PARIS INSTITUTE OF TECHNOLOGY A Simple Searching Problem In the first example,the function returns the index where 4 appears in the list. In the second example,the return value -1 indicates that 7 is not in the list. Python includes a number of built-in search- related methods! 6

6 A Simple Searching Problem • In the first example, the function returns the index where 4 appears in the list. • In the second example, the return value -1 indicates that 7 is not in the list. • Python includes a number of built-in search￾related methods!

上游充通大 ParisTech SHANGHAI JIAO TONG UNIVERSITY INSTITUT DES SCIENCES ET TECHNOLOGIES PARIS INSTITUTE OF TECHNOLOGY A Simple Searching Problem We can test to see if a value appears in a sequence using in. if x in nums: do something If we want to know the position of x in a list,the index method of list can be used. >>>nums=[3,1,4,2,5] >>nums.index (4) 2 7

7 A Simple Searching Problem • We can test to see if a value appears in a sequence using in. if x in nums: # do something • If we want to know the position of x in a list, the index method of list can be used. >>> nums = [3, 1, 4, 2, 5] >>> nums.index(4) 2

上游充通大 ParisTech SHANGHAI JIAO TONG UNIVERSITY INSTITUT DES SCIENCES ET TECHNOLOGIES PARIS INSTITUTE OF TECHNOLOGY A Simple Searching Problem The only difference between our search function and index is that index raises an exception if the target value does not appear in the list. We could implement search using index by simply catching the exception and returning-1 for that case. 8

8 A Simple Searching Problem • The only difference between our search function and index is that index raises an exception if the target value does not appear in the list. • We could implement search using index by simply catching the exception and returning -1 for that case

上游充通大学 ParisTech SHANGHAI JIAO TONG UNIVERSITY INSTITUT DES SCIENCES ET TECHNOLOGIES PARIS INSTITUTE OF TECHNOLOGY A Simple Searching Problem ·def search(x,nums): try: return nums.index (x) except: return -1 Sure,this will work,but we are really interested in the algorithm used to actually search the list in Python! 9

9 A Simple Searching Problem • def search(x, nums): try: return nums.index(x) except: return -1 • Sure, this will work, but we are really interested in the algorithm used to actually search the list in Python!

上游充通大 ParisTech SHANGHAI JIAO TONG UNIVERSITY INSTITUT DES SCIENCES ET TECHNOLOGIES PARIS INSTITUTE OF TECHNOLOGY Strategy 1:Linear Search The natural way to find (or not find)a number in a list is to start at the top of the list,scanning every element and comparing it with the number.Either you find it or you reach the end of the list allows you to answer. This strategy is called a linear search,where you search through the list of items one by one until the target value is found. def search(x,nums）: for i in range(len (nums)): if nums[i]==x:item found,return the index value return i return -1 loop finished,item was not in list This algorithm wasn't hard to develop,and works well for modest-sized lists. 10

10 Strategy 1: Linear Search • The natural way to find (or not find) a number in a list is to start at the top of the list, scanning every element and comparing it with the number. Either you find it or you reach the end of the list allows you to answer. • This strategy is called a linear search, where you search through the list of items one by one until the target value is found. • def search(x, nums): for i in range(len(nums)): if nums[i] == x: # item found, return the index value return i return -1 # loop finished, item was not in list • This algorithm wasn’t hard to develop, and works well for modest-sized lists