上游充通大 ParisTech SHANGHAI JIAO TONG UNIVERSITY INSTITUT DES SCIENCES ET TECHNOLOGIES PARIS INSTITUTE OF TECHNOLOGY Strategy 2:Binary Search search(x,nums) 1ow=0 high=1en(nums）-1 十--=----> <1ow<=high>--------->(return-1) Iy mid =(low high)/2 item=nums[mid】 3 x =item >---------(return mid) In x item >-----high mid 1 81 0百 In low mid 1 80 2 88 a 16
Strategy 2: Binary Search 16
上游充通大 ParisTech SHANGHAI JIAO TONG UNIVERSITY INSTITUT DES SCIENCES ET TECHNOLOGIES PARIS INSTITUTE OF TECHNOLOGY Strategy 2:Binary Search def search(x,nums): 10w=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 of range low mid 1 move bottom marker up return -1 No range left to search, x is not there 17
17 Strategy 2: Binary Search 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 of range low = mid + 1 # move bottom marker up return -1 # No range left to search, # x is not there
上游充通大 ParisTech SHANGHAI JIAO TONG UNIVERSITY INSTITUT DES SCIENCES ET TECHNOLOGIES PARIS INSTITUTE OF TECHNOLOGY Comparing Algorithms Which search algorithm is better,linear or binary? The linear search is easier to understand and implement The binary search is more efficient since it doesn't need to look at each element in the list Intuitively,we might expect the linear search to work better for small lists,and binary search for longer lists.But how can we be sure? 18
18 Comparing Algorithms • Which search algorithm is better, linear or binary? – The linear search is easier to understand and implement – The binary search is more efficient since it doesn’t need to look at each element in the list • Intuitively, we might expect the linear search to work better for small lists, and binary search for longer lists. But how can we be sure?
上游充通大 ParisTech SHANGHAI JIAO TONG UNIVERSITY INSTITUT DES SCIENCES ET TECHNOLOGIES PARIS INSTITUTE OF TECHNOLOGY Comparing Algorithms One way to conduct the test would be to code up the algorithms and try them on varying sized lists, noting the runtime. Linear search is generally faster for lists of length 10 or less There was little difference for lists of 10-1000 - Binary search is best for 1000+(for one million list elements,binary search averaged .0003 seconds while linear search averaged 2.5 second) 19
19 Comparing Algorithms • One way to conduct the test would be to code up the algorithms and try them on varying sized lists, noting the runtime. – Linear search is generally faster for lists of length 10 or less – There was little difference for lists of 10-1000 – Binary search is best for 1000+ (for one million list elements, binary search averaged .0003 seconds while linear search averaged 2.5 second)
上游充通大 ParisTech SHANGHAI JIAO TONG UNIVERSITY INSTITUT DES SCIENCES ET TECHNOLOGIES PARIS INSTITUTE OF TECHNOLOGY Comparing Algorithms While interesting,can we guarantee that these empirical results are not dependent on the type of computer they were conducted on,the amount of memory in the computer,the speed of the computer,etc.? We could abstractly reason about the algorithms to determine how efficient they are.We can assume that the algorithm with the fewest number of“steps”is more efficient. 20
20 Comparing Algorithms • While interesting, can we guarantee that these empirical results are not dependent on the type of computer they were conducted on, the amount of memory in the computer, the speed of the computer, etc.? • We could abstractly reason about the algorithms to determine how efficient they are. We can assume that the algorithm with the fewest number of “steps” is more efficient