上游充通大 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