程序代写代做代考 go algorithm COMP 250

COMP 250
INTRODUCTION TO COMPUTER SCIENCE
Week 9-3 : Recursion 2 (Binary Search)
Giulia Alberini, Fall 2020

WHAT ARE WE GOING TO DO IN THIS VIDEO?
More recursive algorithms
 Decimal to Binary conversion Power function
Binary Search

RECALL: DECIMAL TO BINARY (ITERATIVE)
ALGORITHM Constructing Base 2 Expansions
procedure BinaryExpansion(𝑛) 𝑘≔0
While 𝑛 > 0
𝑎𝑘 ≔ 𝑛%2 n≔ 𝑛/2 𝑘≔𝑘+1
return (𝑎𝑘−1, … , 𝑎1, 𝑎0)
Recall that a decimal number 𝑛 requires approximately log2 𝑛 bits for its binary representation.

DECIMAL TO BINARY (RECURSIVE)
ALGORITHM Constructing Base 2 Expansions
procedure BinaryExpansion(𝑛) If 𝑛 > 0:
BinaryExpansion(𝑛/2) print(𝑛%2)
Also in this case, there are log2 𝑛 recursive calls

POWER (𝑥𝑛) – DEFINITION Definition of power
Inductive definition:  Base clause:
 Inductive clause:
𝑥𝑛 =𝑥⋅𝑥⋯𝑥
𝑛 times
𝑥0 = 1
𝑥𝑛 =𝑥⋅𝑥𝑛−1

POWER (𝑥𝑛) – ITERATIVE 1
Let 𝑥 a positive integer and let 𝑛 be a positive number.
power(x, n) {
int result =1;
for(int i=1; i<=n; i++) { result = result *x; } return result; } POWER (𝑥𝑛) – RECURSIVE power(x, n) { if(n==0) { return 1; } else { return x*power(x,n-1); } } POWER() – CAN WE DO BETTER? More interesting approach using recursion: 𝑥18 = 𝑥9∗𝑥9 𝑥9 = 𝑥4∗𝑥4∗𝑥 𝑥4 = 𝑥2∗𝑥2 𝑥2 = 𝑥∗𝑥 POWER (𝑥𝑛) – RECURSIVE 2 power( x, n) { if (n == 0) return 1; else if (n == 1) return x; else{ tmp = power(x, n/2); if (n%2==0) return tmp*tmp; else // one multiplication return tmp*tmp*x; // two multiplications } } A SIMILAR IDEA CAN BE IMPLEMENTED ITERATIVELY IDEA: Let’s use the binary expansion of 𝑛, say 𝑛 = 𝑎𝑘−1, ... , 𝑎1, 𝑎0 2. Note that: 𝑥𝑛 = 𝑥𝑎𝑘−12𝑘−1+⋯+𝑎12+𝑎0 = 𝑥𝑎𝑘−12𝑘−1 ⋯ 𝑥𝑎12 ⋅ 𝑥𝑎0 This shows how to compute 𝑥𝑛: we only need to compute the values of 𝑥, 𝑥2, 𝑥2 2 = 𝑥4,...,𝑥2𝑘. Once we have these terms we multiply the terms𝑥2𝑗,where𝑎 =1. 𝑗 POWER (𝑥𝑛) – ITERATIVE 2 power(x, n) { result = 1; pow = x; if(n%2 == 1) result = x; n = n/2; while(n != 0) { pow = pow * pow; if(n%2 == 1) Let𝑛= 𝑎𝑘−1,...,𝑎1,𝑎0 2 // log2(𝑛)−1 iterations // 1 multiplication result = result * pow; // 1 multiplication n = n/2; } return result; } POWER (𝑥𝑛) – ITERATIVE 2 power(x, n) { result = 1; pow = x; if(n%2 == 1) result = x; n = n/2; while(n != 0) { pow = pow * pow; if(n%2 == 1) Let 𝑛 = 𝒂𝒌−𝟏,...,𝒂𝟏,𝒂𝟎 2 // log2(𝑛)−1 iterations // 1 multiplication result = result * pow; // 1 multiplication n = n/2; } return result; } POWER (𝑥𝑛) – ITERATIVE 2 power(x, n) { result = 1; pow = x; if(n%2 == 1) result = x; n = n/2; while(n != 0) { pow = pow * pow; if(n%2 == 1) Let 𝑛 = 𝒂𝒌−𝟏,...,𝒂𝟏,𝑎0 2 // log2(𝑛)−1 iterations // 1 multiplication result = result * pow; // 1 multiplication n = n/2; } return result; } EXAMPLE: 𝑥243 𝑛 = (243)10 = (11110011)2 Q: How many multiplications do we need? EXAMPLE: 𝑥243 𝑛 = (243)10 = (11110011)2 Q: How many multiplications do we need? A: Recursive method: 5*2 + 2*1 = 12. Iterative method: 7 + 5 = 12 The highest order bit in the recursive method is the base case, and doesn’t require a multiplication. The lowest order bit in the iterative method does not require multiplication. EXAMPLE: 𝑥243 𝑛 = (243)10 = (11110011)2 Q: How many multiplications do we need? A: 𝑂(log𝑛) OBSERVATIONS The second approach we looked at uses fewer multiplications than the first one, and thus the second approach seems faster. Q: Is this indeed the case? A: No. Why not ? OBSERVATIONS Hint: Let 𝑥 be a positive integer with M digits. 𝑥2 has about ? digits. 𝑥3 has about ? digits. : 𝑥𝑛 has about ? digits. OBSERVATIONS Hint: Let 𝑥 be a positive integer with M digits. 𝑥2 has about 2M digits. 𝑥3 has about 3M digits. : 𝑥𝑛 has about 𝑛 ∗ M digits. We cannot assume that multiplication takes ‘constant’ time. Taking large powers gives very large numbers and multiplications becomes more expensive. BINARY SEARCH SEARCHING A LIST  Goal: find a given element in a list.  Solution: go through all the elements in the list and check whether the element is there (linear search). Could we do this any faster if the list was sorted to begin with? Think of how you search for a term in an index. Do you start at the beginning and then scan through to the end? (No.) BINARY SEARCH  Inputs:  A sorted list.  The element we are looking for (the key)  IDEA: First compare the key with the element in the middle of the list  If the key is less than the middle element, we only need to search the first half of the list, so we continue searching on this smaller list.  If the key is greater than the middle element, we only need to search the second half of the list, so we continue searching on this smaller list.  If the key equals the middle element, we have a match – return its index. http://www.oxfordmathcenter.com/drupal7/node/31 EXAMPLE  Search for 25 1 5 31 35 -4 6 14 23 52 70 EXAMPLE  Search for 25  Look at the middle element and compare 1 5 31 35 -4 6 14 23 52 70 EXAMPLE  Search for 25  Look at the middle element and compare  If not equal: discard half of the list and keep searching on the other half 31 35 -4 1 5 6 14 23 52 70 EXAMPLE  Search for 25  Look at the middle element and compare 31 35 -4 1 5 6 14 23 52 70 EXAMPLE  Search for 25  Look at the middle element and compare  If not equal: discard half of the list and keep searching on the other half -4 1 5 6 14 23 31 35 52 70 EXAMPLE  Search for 25  Look at the middle element and compare -4 1 5 6 14 23 31 35 52 70 EXAMPLE  Search for 25  Look at the middle element and compare  If not equal: discard half of the list and keep searching on the other half -4 1 5 6 14 23 31 35 52 70 EXAMPLE  Search for 25  Look at the middle element and compare -4 1 5 6 14 23 31 35 52 70 EXAMPLE  Search for 25  Look at the middle element and compare  If not equal: discard half of the list and keep searching on the other half -4 1 5 6 14 23 31 35 52 70 EXAMPLE  Search for 25 There are no more elements in the listthe element is not there! Return -1. -4 1 5 6 14 23 31 35 52 70 IMPLEMENT BINARY SEARCH  Idea: keep track of the left and right indices denoting the section of the list that needs to be searched.  What is the index of the element that we compare to the key as a function of the left and right indices? BACK TO EXAMPLE  Search for 25 (initialize left and right) 1 5 31 35 -4 6 14 23 52 70 left = 0 right = 9 right = size -1 BACK TO EXAMPLE  Search for 25  Look at the middle element and compare (compute mid) mid = (left+right)/2 mid = 4 1 5 31 35 -4 6 14 23 52 70 left = 0 right = 9 BACK TO EXAMPLE  Search for 25  Look at the middle element and compare  If not equal: discard half of the list and keep searching on the other half (update left) mid = 4 31 35 -4 1 5 6 14 23 left = 5 right = 9 left = mid +1 52 70 EXAMPLE  Search for 25  Look at the middle element and compare (compute mid) mid = (left+right)/2 =7 31 35 -4 1 5 6 14 23 52 70 left = 5 right = 9 EXAMPLE  Search for 25  Look at the middle element and compare  If not equal: discard half of the list and keep searching on the other half (update right) mid = 7 -4 1 5 6 14 23 31 35 52 70 left=5 right=6 = mid -1 EXAMPLE  Search for 25  Look at the middle element and compare (compute mid) mid = 5 -4 1 5 6 14 23 31 35 52 70 left=5 right=6 EXAMPLE  Search for 25  Look at the middle element and compare  If not equal: discard half of the list and keep searching on the other half (update left) mid = 5 -4 1 5 6 14 23 31 35 52 70 left = 6 right = 6 EXAMPLE  Search for 25  Look at the middle element and compare (compute mid) mid = 6 -4 1 5 6 14 23 31 35 52 70 left = 6 right = 6 EXAMPLE  Search for 25  Look at the middle element and compare  If not equal: discard half of the list and keep searching on the other half (update right) mid = 6 -4 1 5 6 14 23 31 35 52 70 right= 5 left = 6 EXAMPLE  Search for 25  There are no more elements in the list (right