上游充通大 ParisTech SHANGHAI JIAO TONG UNIVERSITY INSTITUT DES SCIENCES ET TECHNOLOGIES PARIS INSTITUTE OF TECHNOLOGY Strategy 1:Linear Search The Python in and index operations both implement linear searching algorithms. If the collection of data is very large,it makes sense to organize the data somehow so that each data value doesn't need to be examined. 11
11 Strategy 1: Linear Search • The Python in and index operations both implement linear searching algorithms. • If the collection of data is very large, it makes sense to organize the data somehow so that each data value doesn’t need to be examined
上游充通大 ParisTech SHANGHAI JIAO TONG UNIVERSITY INSTITUT DES SCIENCES ET TECHNOLOGIES PARIS INSTITUTE OF TECHNOLOGY Strategy 1:Linear Search If the data is sorted in ascending order (lowest to highest),we can skip checking some of the data. As soon as a value is encountered that is greater than the target value,the linear search can be stopped without looking at the rest of the data. On average,this will save us about half the work. 12
12 Strategy 1: Linear Search • If the data is sorted in ascending order (lowest to highest), we can skip checking some of the data. • As soon as a value is encountered that is greater than the target value, the linear search can be stopped without looking at the rest of the data. • On average, this will save us about half the work
上游充通大 ParisTech SHANGHAI JIAO TONG UNIVERSITY INSTITUT DES SCIENCES ET TECHNOLOGIES PARIS INSTITUTE OF TECHNOLOGY Strategy 2:Binary Search Given an ordered list We can use two variables to keep track of the endpoints of the range in the sorted list where the number could be. Since the target could be anywhere in the list, initially low is set to the first location in the list,and high is set to the last. 13
13 Strategy 2: Binary Search • Given an ordered list • We can use two variables to keep track of the endpoints of the range in the sorted list where the number could be. • Since the target could be anywhere in the list, initially low is set to the first location in the list, and high is set to the last
上降充通大 ParisTech SHANGHAI JIAO TONG UNIVERSITY INSTITUT DES SCIENCES ET TECHNOLOGIES PARIS INSTITUTE OF TECHNOLOGY Strategy 2:Binary Search The heart of the algorithm is a loop that looks at the middle element of the range,comparing it to the value x. If x is smaller than the middle item,high is moved so that the search is confined to the lower half. If x is larger than the middle item,1ow is moved to narrow the search to the upper half. 14
14 Strategy 2: Binary Search • The heart of the algorithm is a loop that looks at the middle element of the range, comparing it to the value x. • If x is smaller than the middle item, high is moved so that the search is confined to the lower half. • If x is larger than the middle item, low is moved to narrow the search to the upper half
上游充通大 ParisTech SHANGHAI JIAO TONG UNIVERSITY INSTITUT DES SCIENCES ET TECHNOLOGIES PARIS INSTITUTE OF TECHNOLOGY Strategy 2:Binary Search The loop terminates when either -x is found There are no more places to look (1ow high) 15
15 Strategy 2: Binary Search • The loop terminates when either – x is found – There are no more places to look (low > high)